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 non-adiabatic effects. Those effects suppress the phonon life times at low temperature compared to an adiabatic approach. The here identified dynamic coupling provides an explanation for the experimentally observed unexpected temperature dependence of the thermal conductivity of magnetic semiconductors above the magnetic ordering temperature.