We investigate the excitation spectrum of strongly correlated sodium cobaltate within a realistic many-body description beyond dynamical mean-field theory (DMFT). At lower doping around x=0.3, rather close to Mott-critical half-filling, the single-particle spectral function of NaxCoO2 displays an upper Hubbard band which is captured within DMFT. Momentum-dependent self-energy effects beyond DMFT become dominant at higher doping. Around a doping level of x∼0.67, the incoherent excitations give way to finite-energy spin-polaron excitations in close agreement with optics experiments. These excitations are a direct consequence of the formation of bound states between quasiparticles and paramagnons in the proximity of in-plane ferromagnetic ordering.