We consider the role played by the 4f states in the rare-earth oxyarsenides REOFeAs (RE=Ce, Pr, Nd) and the oxyphosphate CeOFeP, using a first-principles technique that combines the local density approximation and dynamical mean-field theory (LDA+DMFT). In the Pr and Nd compounds, the 4f states are located well below and above the Fermi level E_F, and essentially do not interact with the iron 3d bands located near E_F, resulting in local moment behavior. In the Ce compounds, our results reveal a qualitatively different picture, with the 3d-4f hybridization being sufficiently strong to give rise to an observable Kondo screening of the local 4f moment. Our LDA+DMFT electronic structure calculations allow us to estimate the Kondo temperature T_K for both CeOFeP and CeOFeAs. For the phosphate, the order of magnitude of our estimate is consistent with the experimental observation of T_K~10 K. At ambient pressure, T_K is found to be negligibly small for CeOFeAs. Under applied hydrostatic pressure, we predict an exponential increase of T_K which reaches values comparable to the superconducting T_c~40 K at pressures above 10 GPa. We conjecture that the competition between the Kondo effect and superconductivity may be at the origin of the monotonous decrease of T_c observed in CeOFeAs under pressure. We argue that the quantitative aspects of this competition are inconsistent with a weak-coupling BCS description of the superconductivity in the oxyarsenides.