We provide definitive theoretical evidence for the onset of superfluidity in small helium clusters doped with molecules at less than one solvation shell, with quantitative analysis of spectroscopic constants for CO2 in (4)He(N) in terms of nonclassical rotational inertia and helium superfluidity calculated by path integral methods. We find a significant superfluid response for N>/=5, with essentially unit response to rotations around the CO2 axis and partial response to rotations about an axis perpendicular to the CO2 axis for N>/=6. This anisotropic superfluid response is shown to be responsible for the N dependence of measured CO2 rotational spectra in (4)He(N).