The transient interactions of proteins and other molecules with much larger structures, such as synthetic or biological nanoparticles, lead to certain types of enhanced nuclear magnetic resonance (NMR) spin relaxation effects, which can be accurately measured by multidimensional solution NMR techniques. These relaxation effects provide new information about the nanostructures and the protein, their interactions, internal dynamics, and associated kinetic and thermodynamic parameters, such as exchange rates and populations. Although theoretical treatments exist that cover either the fast or slow exchange limits, a theoretical treatment that applies to all practically relevant exchange processes is still missing. A unified theoretical framework is presented for this purpose based on a stochastic Liouville equation (SLE). It covers nuclear spin dynamics, overall rotational diffusion of both the protein and the nanostructure, the exchange process between a free state and a bound state, and internal protein dynamics. Although the numerical implementation of the SLE typically involves large matrices, it is shown here that it is computationally still tractable for situations relevant in practice. Application of the theory demonstrates how transverse relaxation is substantially impacted by the kinetics of binding on a wide range of exchange timescales. It is further shown that when exchange occurs on the appropriate timescale, transverse relaxation is able to report on internal dynamics far slower than observable by traditional transverse relaxation experiments. The SLE will allow the realistic and quantitative interpretation of experimental NMR data reporting about transient protein-nanoparticle interactions, thereby providing a powerful tool for the characterization of protein dynamics modes on a vast range of timescales including motions that may be functionally relevant.