We study the mutual coupling of spin fluctuations and lattice vibrations in paramagnetic CrN by combining atomistic spin dynamics and ab initio molecular dynamics. The two degrees of freedom are dynamically coupled, leading to nonadiabatic effects. Those effects suppress the phonon lifetimes at low temperature compared to an adiabatic approach. The dynamic coupling identified here provides an explanation for the experimentally observed unexpected temperature dependence of the thermal conductivity of magnetic semiconductors above the magnetic ordering temperature.