Scintillating CaWO$_4$ single crystals are a promising multi-element target for rare-event searches and are currently used in the direct Dark Matter experiment CRESST (Cryogenic Rare Event Search with Superconducting Thermometers). The relative light output of different particle interactions in CaWO$_4$ is quantified by Quenching Factors (QFs). These are essential for an active background discrimination and the identification of a possible signal induced by weakly interacting massive particles (WIMPs). We present the first precise measurements of the QFs of O, Ca and W at mK temperatures by irradiating a cryogenic detector with a fast neutron beam. A clear energy dependence of the QF of O and, less pronounced, of Ca was observed for the first time. Furthermore, in CRESST neutron-calibration data a variation of the QFs among different CaWO$_4$ single crystals was found. For typical CRESST detectors the QFs in the region-of-interest (10-40$\,$keV) are $QF_O^{ROI}=(11.2{\pm}0.5)\,$%, $QF_{Ca}^{ROI}=(5.94{\pm}0.49)\,$% and $QF_W^{ROI}=(1.72{\pm}0.21)\,$%. The latest CRESST data (run32) is reanalyzed using these fundamentally new results on light quenching in CaWO$_4$ having moderate influence on the WIMP analysis. Their relevance for future CRESST runs and for the clarification of previously published results of direct Dark Matter experiments is emphasized.