First-principles calculations of the effect of carbon coverage on the atomic, electronic and magnetic structure of nickel and iron substrates demonstrate insignificant changes in the interatomic distances and magnetic moments on the atoms of the metallic substrates. The coverage of the iron surface by mono- and few-layer graphene induces significant changes in the orbital occupancies and exchange interactions between the layers in contrast to the case of a nickel substrate for which changes in the orbital ordering and exchange interactions are much smaller. Experimental measurements demonstrate the presence of ferromagnetic fcc-iron in Fe@C nanoparticles and the superparamagnetic behavior of Ni@C nanoparticles.