Phonon-assisted electronic tunnelings through a vibrating quantum dot embedded between normal and superconducting leads are studied in the Kondo regime. In such a hybrid device, with the bias applied to the normal lead, we find a series of Kondo sidebands separated by half a phonon energy in the differential conductance, which are distinct from the phonon-assisted sidebands previously observed in the conventional Andreev tunnelings and in systems with only normal leads. These Kondo sidebands originate from the Kondo-Andreev cooperative cotunneling mediated by phonons, which exhibit a novel Kondo transport behavior due to the interplay of the Kondo effect, the Andreev tunnelings, and the mechanical vibrations. Our result could be observed in a recent experiment setup [J. Gramich emph{et al.}, PRL textbf{115}, 216801 (2015)], provided that their carbon nanotube device reaches the Kondo regime at low temperatures.