A combination of theoretical modelling and experiments reveals the origin of the large perpendicular magnetic anisotropy (PMA) that appears in nanometer-thick epitaxial Co films intercalated between graphene (Gr) and a heavy metal (HM) substrate, as a function of the Co thickness. High quality epitaxial Gr/Co /HM(111) (HM=Pt,Ir) heterostructures are grown by intercalation below graphene, which acts as a surfactant that kinetically stabilizes the pseudomorphic growth of highly perfect Co face-centered tetragonal ($fct$) films, with a reduced number of stacking faults as the only structural defect observable by high resolution scanning transmission electron microscopy (HR-STEM). Magneto-optic Kerr effect (MOKE) measurements show that such heterostructures present PMA up to large Co critical thicknesses of about 4~nm (20~ML) and 2~nm (10~ML) for Pt and Ir substrates, respectively, while X-ray magnetic circular dichroism (XMCD) measurements show an inverse power law of the anistropy of the orbital moment with Co thickness, reflecting its interfacial nature, that changes sign at about the same critical values. First principles calculations show that, regardless of the presence of graphene, ideal Co $fct$ films on HM buffers do not sustain PMAs beyond around 6~MLs due to the in-plane contribution of the inner bulk-like Co layers. The large experimental critical thicknesses sustaining PMA can only be retrieved by the inclusion of structural defects that promote a local $hcp$ stacking such as twin boundaries or stacking faults. Remarkably, a layer resolved analysis of the orbital momentum anisotropy reproduces its interfacial nature, and reveals that the Gr/Co interface contribution is comparable to that of the Co/Pt(Ir).