Indeed, the set of primes is not implicitly definable over $(\mathbb{N},S)$. This is shown by the following:

Theorem. A unary predicate $P$ on $\mathbb{N}$ is implicitly definable in $(\mathbb{N},S)$ iff $P$ is a finally periodic set of naturals.

Proof. Suppose $P$ is finally periodic, i.e. there are naturals $n$ and $m>0$ such that $\forall x(x\ge n \to x\in P\mathrel{\leftrightarrow} x+m\in P)$. Then $P$ is implicitly definable by the following formula $\varphi(X)$: $$\forall x\Big(X(x)\mathrel{\leftrightarrow}\exists y,z\big( S^{n+m}(z)=x\land S^m(y)=x\land X(y)\big) \lor \bigvee\limits_{k<n+m\text{ and }k\in P}x=S^k(0)\Big)$$

On the other hand if $P$ is implicitly definable in $(\mathbb{N},S)$, then it is definable in $(\mathbb{N},S)$ by a monadic second-order formula. And by the classical result of Büchi a set of naturals has a monadic second-order definition in $(\mathbb{N},S)$ iff it is finally periodic (combination of results from [1] and [2]).QED

[1]Büchi, J. Richard. "Symposium on Decision Problems: On a Decision Method in Restricted Second Order Arithmetic." Studies in Logic and the Foundations of Mathematics. Vol. 44. Elsevier, 1966. 1-11.

[2]Büchi, J. R. “Weak Second Order Arithmetic and Finite Automata”, Zeitschrift für Math. Log. und Grundl. der Math., 6 (1960), pp. 66–92.

Indeed, the set of primes is not implicitly definable over $(\mathbb{N},S)$. I gave a proof of this in an answer to the question of Geoffrey Irving. See https://mathoverflow.net/a/426382/36385 .