There is some $N(k, p)$ such that $n \ge N(k, p) \implies s(n, k) \equiv 0 \pmod p$. Proof is straightforward by fixing $p$ and using induction on $k$ via the recurrence $$s(n, k) = s(n-1, k-1) - (n-1)s(n-1, k).$$ In fact, the same proof idea shows that $N(k, p) \le kp+1$ so this allows for effective testing of $(k, p)$. Fedor Petrov's first comment on the question hints at this.

Fedor's second comment argues heuristically that counterexamples should exist. In practice, the counterexamples seem to be much smaller than the $e^k$ that the heuristic suggests.

$$\begin{array}{ccc} k & p & \textrm{Uncovered residues} \\ 12 & 509 & \{150\} \\ 13 & 2243 & \{1761\} \\ 14 & 5233 & \{1128\} \\ 15 & 5233 & \{4105\} \\ 16 & 5233 & \{1128\} \\ 17 & 5233 & \{4105\} \\ 18 & 5233 & \{1128\} \\ \end{array}$$

For $k=19$ I've checked up to $p=13327$ without finding a counterexample, but since the heuristic suggests looking at primes on the order of $178482301$ that's not really saying much.

There is some $N(k, p)$ such that $n \ge N(k, p) \implies s(n, k) \equiv 0 \pmod p$. Proof is straightforward by fixing $p$ and using induction on $k$ via the recurrence $$s(n, k) = s(n-1, k-1) - (n-1)s(n-1, k).$$ In fact, the same proof idea shows that $N(k, p) \le kp+1$ so this allows for effective testing of $(k, p)$. Fedor Petrov's first comment on the question hints at this.

Fedor's second comment argues heuristically that counterexamples should exist in primes of the order of $e^k$. In practice, the smallest counterexamples seem to be much smaller than that.

$$\begin{array}{ccc} k & p & \textrm{Uncovered residues} \\ 12 & 509 & \{150\} \\ 13 & 2243 & \{1761\} \\ 14 & 5233 & \{1128\} \\ 15 & 5233 & \{4105\} \\ 16 & 5233 & \{1128\} \\ 17 & 5233 & \{4105\} \\ 18 & 5233 & \{1128\} \\ 19 & 73681 & \{926\} \\ 20 & 153611 & \{108851\} \\ 21 & 212671 & \{50455\} \\ 22 & 232129 & \{169472\} \\ \end{array}$$