Let $n = k m^{d+1}$. We will construct the desired splitting in the following way. To determine which of the subsets each number $x \in \{1; 2; \dots n\}$ belongs to, let us write $x - 1$ in the form:
$$x - 1 = c m^{d+1} + x_0 + x_1 m + x_2 m^2 + \dots + x_d m^d,$$
where $c \ge 0$ is an integer, $x_i \in \{0; 1; \dots m-1\}$, $i = 0, \dots, d$, i.e. we write the remainder of $x-1$ divided by $m^{d+1}$ in base $m$ numeral system. We include the number $x$ to subset $A_j$, $j \in \{1; 2; \dots m\}$ if $x_0 + x_1 + x_2 + \dots + x_d \equiv j \pmod m$. Let us show that such splitting satisfies the condition. Clearly, it is enough to prove our statement for polynomials of the form $P(x) = x^t$, $t = 0, \dots, d$.

We have
$$S(A_j) = \sum_{c=0}^{k-1} \sum_j (c m^{d+1} + x_0 + x_1 m + x_2 m^2 + \dots + x_d m^d)^t,$$
where $\sum_j$ denotes the sum over all tuples $x_0, \dots, x_d$ of numbers from the set $\{0; 1; \dots m-1\}$ such that $x_0 + x_1 + x_2 + \dots + x_d \equiv j \pmod m$. Let us show that the inner sum does not depend on $j$. Denoting $z = 1 + c m^{d+1}$, we can transform it by expanding the brackets:
$$\sum_j (c m^{d+1} + x_0 + x_1 m + x_2 m^2 + \dots + x_d m^d)^t = \sum_d \frac{t!}{u! t_0! t_1! \dots t_d!} z^u m^{t_1 + 2 t_2 + \dots + d t_d} \sum_j x_0^{t_0} x_1^{t_1} \dots x_d^{t_d},$$
where $\sum_d$ denotes the sum over all tuples of non-negative integers $u, t_0, \dots, t_d$ such that $u + t_0 + \dots + t_d = t$. Since $t_0 + \dots + t_d \le t < d+1$, there is at least one number among $t_0, \dots, t_d$ which equals zero. Suppose that $t_0 = 0$, then
$$\sum_j x_0^{t_0} x_1^{t_1} \dots x_d^{t_d} = \sum_j x_1^{t_1} \dots x_d^{t_d} = \sum_{x_1, \dots, x_d = 0}^{m-1} x_1^{t_1} \dots x_d^{t_d},$$
because for any tuple $x_1, \dots, x_d$ of numbers from $\{0; 1; \dots m-1\}$ there is a unique number $x_0 \in \{0; 1; \dots m-1\}$ for which $x_0 + x_1 + x_2 + \dots + x_d \equiv j \pmod m$. The last sum is clearly independent of $j$, which is what we wanted to prove.