The main observation is that $P(x)$ is just $(x^{\frac13} + 1)^3$ in modulo $p$. With this insight, and the fact that the map $x \rightarrow x^3$ is bijective in mod $p$, we can consider defining the set $T = \{ x^{\frac13} | x \in S\}$. The first operation just adds one to each element of $T$ and the second just raises them all to the power of $T$. We can further make the assumption that whenever the second operation results in two numbers in the set becoming equal, we remove one of them. Now the problem is much easier. If $\gcd (k, p-1) = 1$, we clearly cannot reduce $S$ to $\{0\}$ since $T$ never changes. Now, suppose that $\gcd (k, p-1) > 1.$ Let $a$ be a positive integer such that $p|a^k - 1$ and $p \nmid a-1.$ Then, suppose that $|T| \ge 2$ at some point in time. Let $d$ be the difference between some two arbitrary distinct elements of $T$. Since $p \nmid a-1$, there exists a $x$ such that $ax \equiv x + d$. Then, simply apply the first operation sufficiently many times until $x, ax \in T.$ Now, appllying the second operation decreases the size of $T$ strictly. Repeating this finishes. $\square$