We develop a first-principles model of thermally-activated cross-slip in magnesium in the presence of a random solute distribution. Electronic structure methods provide data for the interaction of solutes with prismatic dislocation cores and basal dislocation cores. Direct calculations of interaction energies are possible for solutes---K, Na, and Sc---that lower the Mg prismatic stacking fault energy to improve formability. To connect to thermally activated cross-slip, we build a statistical model for the distribution of activation energies for double kink nucleation, barriers for kink migration, and roughness of the energy landscape to be overcome by an athermal stress. These distributions are calculated numerically for a range of concentrations, as well as alternate approximate analytic expressions for the dilute limit. The analytic distributions provide a simplified model for the maximum cross-slip softening for a solute as a function of temperature. The direct interaction calculations predict lowered forming temperatures for Mg-0.7at.%Sc, Mg-0.4at.%K, and Mg-0.6at.%Na of approximately 250C.