Spin waves have risen as promising candidate information carriers for the next generation of information technologies. Recent experimental demonstrations of their detection using electron spins in diamond pave the way towards studying the back-action of a controllable paramagnetic spin bath on the spin waves. Here, we present a quantum theory describing the interaction between spin waves and paramagnetic spins. As a case study we consider an ensemble of nitrogen-vacancy spins in diamond in the vicinity of an Yttrium-Iron-Garnet thin film. We show how the back-action of the ensemble results in strong and tuneable modifications of the spin-wave spectrum and propagation properties. These modifications include the full suppression of spin-wave propagation and, in a different parameter regime, the enhancement of their propagation length by $sim 50%$. Furthermore, we show how the spin wave thermal fluctuations induce a measurable frequency shift of the paramagnetic spins in the bath. This shift results in a thermal dispersion force that can be measured optically and/or mechanically with a diamond mechanical resonator. In addition, we use our theory to compute the spin wave-mediated interaction between the spins in the bath. We show that all the above effects are measurable by state-of-the-art experiments. Our results provide the theoretical foundation for describing hybrid quantum systems of spin waves and spin baths, and establish the potential of quantum spins as active control, sensing, and interfacing tools for spintronics.