The development of cryogenic semiconductor electronics and superconducting quantum computing requires composite materials that can provide both thermal conduction and thermal insulation. We demonstrated that at cryogenic temperatures, the thermal conductivity of graphene composites can be both higher and lower than that of the reference pristine epoxy, depending on the graphene filler loading and temperature. There exists a well-defined cross-over temperature—above it, the thermal conductivity of composites increases with the addition of graphene; below it, the thermal conductivity decreases with the addition of graphene. The counter-intuitive trend was explained by the specificity of heat conduction at low temperatures: graphene fillers can serve as, both, the scattering centers for phonons in the matrix material and as the conduits of heat. We offer a physical model that explains the experimental trends by the increasing effect of the thermal boundary resistance at cryogenic temperatures and the anomalous thermal percolation threshold, which becomes temperature dependent. The obtained results suggest the possibility of using graphene composites for, both, removing the heat and thermally insulating components at cryogenic temperatures—a capability important for quantum computing and cryogenically cooled conventional electronics.