We employ density-functional theory (DFT) in the generalized gradient approximation (GGA) and its extensions GGA+$U$ and GGA+Gutzwiller to calculate the magnetic exchange couplings between pairs of Mn ions substituting Cd in a CdTe crystal at very small doping. DFT(GGA) overestimates the exchange couplings by a factor of three because it underestimates the charge-transfer gap in Mn-doped II-VI semiconductors. Fixing the nearest-neighbor coupling $J_1$ to its experimental value in GGA+$U$, in GGA+Gutzwiller, or by a simple scaling of the DFT(GGA) results provides acceptable values for the exchange couplings at 2nd, 3rd, and 4th neighbor distances in Cd(Mn)Te, Zn(Mn)Te, Zn(Mn)Se, and Zn(Mn)S. In particular, we recover the experimentally observed relation $J_4>J_2,J_3$. The filling of the Mn 3$d$-shell is not integer which puts the underlying Heisenberg description into question. However, using a few-ion toy model the picture of a slightly extended local moment emerges so that an integer $3d$-shell filling is not a prerequisite for equidistant magnetization plateaus, as seen in experiment.