We present the direct imaging discovery of an extrasolar planet, or possible low-mass brown dwarf, at a projected separation of 55 plus or minus 2 AU (1."058 plus or minus 0."007) from the B9-type star K And. The planet was detected with Subaru/HiCIAO (Subaru/High Contrast Instrument for the Subaru Next Generation Adaptive Optics) during the SEEDS (Strategic Exploration of Exoplanets and Disks with Subaru Telescope/HiCIAO) survey and confirmed as a bound companion via common proper motion measurements. Observed near-infrared magnitudes of J equals 16.3 plus or minus 0.3, H equals 15.2 plus or minus 0.2, K (sub s) = 14.6 plus or minus 0.4, and L prime equals 13.12 plus or minus 0.09 indicate a temperature of approximately 1700 degrees Kelvin. The galactic kinematics of the host star are consistent with membership in the Columba Association, implying a corresponding age of 30 (exp from plus 20 to minus10) Myr. The systems age, combined with the companion photometry, points to a model-dependent companion mass approximately 12.8 times the mass of Jupiter. The host stars estimated mass of 2.4 to 2.5 times the mass of the sun places it among the most massive stars ever known to harbor an extrasolar planet or low-mass brown dwarf. While the mass of the companion is close to the deuterium burning limit, its mass ratio, orbital separation, and likely planet-like formation scenario imply that it may be best defined as a super-Jupiter with properties similar to other recently discovered companions to massive stars.