The first-discovered interstellar object passing through the Solar System, 1I/2017 (‘Oumuamua), experienced non-gravitational acceleration, yet observational efforts failed to detect common cometary volatiles associated with outgassing. Thus, ‘Oumuamua cannot be strictly analogous to either Solar System asteroids or comets, casting doubt on the protoplanetary disk product premise. In this study, we investigate a Giant Molecular Cloud (GMC) origin - specifically, we further constrain the hypothesis that ‘Oumuamua belongs to a novel class of astronomical objects formed with a sizable component of solid molecular hydrogen. We analyze conditions in cold, dense GMC cores, where nucleation onto 10μm dust aggregates is thermodynamically-favored. “Dirty snowballs” accrete hydrogen via deposition onto the geometric cross-section at all relevant sizes, and at large snowball mass, gravitational-focusing of slower-moving dust becomes important. First, we derive an analytic solution for the simple case of a single, isolated body. Next, we present an approximate analytic method and numerical results for the cases of two-bodies and n-bodies, modeling the simultaneous accretion of material and the gravitational coagulation of macroscopic bodies. From these results, we determine the range of characteristic snowball sizes, which constrains the expected size and metallicity of ‘Oumuamua-like objects after mass loss in the interstellar medium. Finally, we discuss the potential for in-situ detection of molecular hydrogen in future interstellar objects.