We set out to bridge the gap between regular black-hole spacetimes and observations of a black-hole shadow by the Event Horizon Telescope. We explore modifications of spinning and non-spinning black-hole spacetimes inspired by asymptotically safe quantum gravity which features a scale dependence of the Newton coupling. As a consequence, the predictions of our model, such as the shadow shape and size, depend on one free parameter determining the curvature scale at which deviations from General Relativity set in. In more general new-physics settings, it can also depart substantially from the Planck scale. In this case, the free parameter is constrained by observations, since the corresponding curvature scale is significantly below the Planck-scale. The leading new-physics effect can be recast as a scale-dependent black-hole mass, resulting in distinct observational signatures of our model. As a concrete example, we show that two mass-measurements, extracted from the size of the shadow and from Keplerian orbital motion of stars, allow to distinguish the classical from the modified, regular black-hole spacetime, yielding a bound on the free parameter. For spinning black holes, we further find that the singularity-resolving new physics puts a characteristic dent in the shadow. Finally, we argue, based on the underlying physical mechanism, that the effects we derive could be generic consequences of a large class of quantum-gravity theories.