Polynomial multiplications and counting
You already explained what to do when $k = 2$. Let's see what to do when $k = 3$. Let $P_i$ be the polynomial corresponding to $iS$ (for example, the solution for $k = 2$ is $(P_1^2 - P_2)/2$).

We can construct the following table:
$$
\begin{array}{c|ccc}
&amp; aaa &amp; aab &amp; abc \\\hline
P_1^3 &amp; 1 &amp; 1 &amp; 1 \\
3P_2 P_1 &amp; 3 &amp; 1 &amp; 0\\
P_3 &amp; 1 &amp; 0 &amp; 0
\end{array}
$$
So the solution for $k = 3$ is $(P_1^3 - 3P_2P_1 + 2P_3)/6$.

More generally, the solution will involve terms corresponding to all partitions of $k$. The coefficients presumably appear in some change-of-basis formula for symmetric polynomials, and you can find formulas by browsing monographs on the subject.