We predict that a large class of helium-containing cold polar molecules form readily in a cryogenic buffer gas, achieving densities as high as 10(12) cm(-3). We explore the spin relaxation of these molecules in buffer-gas-loaded magnetic traps and identify a loss mechanism based on Landau-Zener transitions arising from the anisotropic hyperfine interaction. Our results show that the recently observed strong T(-6) thermal dependence of the spin-change rate of silver (Ag) trapped in dense (3)He is accounted for by the formation and spin change of Ag(3)He van der Waals molecules, thus providing indirect evidence for molecular formation in a buffer-gas trap.