Ab initio calculations are used to construct an analytical many-body potential for Pb(2+)He(n) and Pb(+)He(n) clusters which accounts for non pairwise additive interactions. The potential surface reproduces the global minima for cluster sizes ranging from n = 1 to n = 16 obtained from explicit ab initio calculations and found in a previous search for ultrahigh coordination numbers. Ground state energies and structures obtained by accurate diffusion quantum Monte Carlo calculations are used to investigate if quantum effects qualitatively affect the formation of coordination shells. For Pb(2+) doped clusters a first solvation shell is closed at n = 12 and gradually softened by additional helium atoms which start to form a distinct second shell only at n = 16. Spin-orbit coupling profoundly influences the structure of Pb(+)He(n) clusters and causes a gradual structural evolution without pronounced solvation shells.