We investigate the excitation spectrum of strongly correlated sodium cobaltate within a realistic many-body description $ \it {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 $Na_{x}CoO_{2}$ 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\sim 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.