The chemical evolution in high-mass star-forming regions is still poorly constrained. Studying the evolution of deuterated molecules allows to differentiate between subsequent stages of high-mass star formation regions due to the strong temperature dependence of deuterium isotopic fractionation. We observed a sample of 59 sources including 19 infrared dark clouds, 20 high-mass protostellar objects, 11 hot molecular cores and 9 ultra-compact HII regions in the (3-2) transitions of the four deuterated molecules, DCN, DNC, DCO+ and N2D+ as well as their non-deuterated counterpart. The overall detection fraction of DCN, DNC and DCO+ is high and exceeds 50% for most of the stages. N2D+ was only detected in a few infrared dark clouds and high-mass protostellar objects. It can be related to problems in the bandpass at the frequency of the transition and to low abundances in the more evolved, warmer stages. We find median D/H ratios of ~0.02 for DCN, ~0.005 for DNC, ~0.0025 for DCO+ and ~0.02 for N2D+. While the D/H ratios of DNC, DCO+ and N2D+ decrease with time, DCN/HCN peaks at the hot molecular core stage. We only found weak correlations of the D/H ratios for N2D+ with the luminosity of the central source and the FWHM of the line, and no correlation with the H2 column density. In combination with a previously observed set of 14 other molecules (Paper I) we fitted the calculated column densities with an elaborate 1D physico-chemical model with time-dependent D-chemistry including ortho- and para-H2 states. Good overall fits to the observed data have been obtained the model. It is one of the first times that observations and modeling have been combined to derive chemically based best-fit models for the evolution of high-mass star formation including deuteration.