Motivated by the premise that superconductivity in iron-based superconductors is unconventional and mediated by spin fluctuations, an intense research effort has been focused on characterizing the spin-excitation spectrum in the magnetically ordered parent phases of the Fe pnictides and chalcogenides. For these undoped materials, it is well established that the spin-excitation spectrum consists of sharp, highly dispersive magnons. The fate of these high-energy magnetic modes upon sizable doping with holes is hitherto unresolved. Here we demonstrate, using resonant inelastic X-ray scattering, that optimally hole-doped superconducting Ba(0.6)K(0.4)Fe(2)As(2) retains well-defined, dispersive high-energy modes of magnetic origin. These paramagnon modes are softer than, though as intense as, the magnons of undoped antiferromagnetic BaFe(2)As(2). The persistence of spin excitations well into the superconducting phase suggests that the spin fluctuations in Fe-pnictide superconductors originate from a distinctly correlated spin state. This connects Fe pnictides to cuprates, for which, in spite of fundamental electronic structure differences, similar paramagnons are present.