We study the Kondo screening of a magnetic impurity adsorbed in graphene in the presence of Rashba spin-orbit interaction. The system is described by an effective single-channel Anderson impurity model, which we analyze using the numerical renormalization group. The nontrivial energy dependence of the host density of states gives rise to interesting behaviors under variation of the chemical potential or the spin-orbit coupling. Varying the Rashba coupling produces strong changes in the Kondo temperature characterizing the many-body screening of the impurity spin, and at half filling allows an approach to a quantum phase transition separating the strong-coupling Kondo phase from a free-moment phase. Tuning the chemical potential close to sharp features of the hybridization function results in striking features in the temperature dependencies of thermodynamic quantities and in the frequency dependence of the impurity spectral function.