Denote $f: \mathbb{Z}_{\ge 0}^2 \to \mathbb{Z}$ such that
$$x^n = f(0, n) + f(1, n)[(x+1)-1] + f(2, n)[(x+1)(x+2) - (x+1)] + \dots$$
for every non-negative integers $x, n$.
The above function always exists because the expression of $x^n$ can be uniquely represented in that particular way. Moreover, $f(x, n)$ is an integer for every $x, n \in \mathbb{Z}_{\ge 0}$ and $f(x, n) = 0$ for all $x > n$. Next, we will prove the following lemmas.

Lemma 1. $f(0, n)$ is even if and only if $3 \mid n - 1$
Proof. Observe that $f(0, 0) = 1$, $f(0, 1) = 1$, and $f(0, 2) = -1$, so it is sufficient to show that $2 \mid f(0, n) + f(0, n + 1) + f(0, n + 2)$ for all $n \in \mathbb{Z}_{\ge 0}$.

Rewrite the definition of $f$ as
$$x^n = g(0, n) + \sum_{i=1}^{n} g(i, n)(x+1)(x+2)\cdots(x+i)$$
where $g(k, n) = f(k, n) - f(k+1, n)$ for all $k, n \in \mathbb{Z}_{\ge 0}$. Therefore,
$$g(0, n) + g(1, n) + \cdots + g(n, n) = \sum_{i=0}^{n} g(i, n) \text{ for all } n \in \mathbb{Z}_{\ge 0}$$

$$\begin{align*} x^{n+1} &= g(0, n) + \sum_{i=1}^{n} g(i, n) \cdot x(x+1)(x+2) \cdots (x+i) \\ &= g(0, n) + \sum_{i=1}^{n} g(i, n) \cdot \left[ (x+1)(x+2) \cdots (x+i)(x+i+1) \right. \\ & \qquad \left. -(i+1)(x+1)(x+2) \cdots (x+i) \right] \\ &= g(n, n)(x+1)(x+2) \cdots (x+n+1) + \sum_{i=1}^{n-1} [g(i-1, n) - (i+1)g(i, n)] \\ & \qquad (x+1)(x+2) \cdots (x+i) - g(0, n) \end{align*}$$

Therefore, $g(n+1, n+1) = g(n, n)$, $g(0, n+1) = -g(0, n)$, and $g(i, n+1) = g(i-1, n) - (i+1)g(i, n)$ for each $1 \le i \le n$. Wrapping them up, we get, for each $n \in \mathbb{Z}_{\ge 0}$,
$$f(0, n + 1) = \sum_{i=0}^{n+1} g(i, n + 1) = - \sum_{i=0}^{n} ig(i, n).$$
And
$$\begin{align*} f(0, n + 2) &= - \sum_{i=0}^{n+1} ig(i, n + 1) \\ &= -(n + 1)g(n, n) - \sum_{i=1}^{n} i[g(i - 1, n) - (i + 1)g(i, n)] \\ &\equiv -(n + 1)g(n, n) - \sum_{i=0}^{n-1} (i + 1)g(i, n) \pmod{2} \\ &\equiv - \sum_{i=0}^{n} (i + 1)g(i, n) \pmod{2} \end{align*}$$
Therefore,
$$\begin{align*} f(0, n) + f(0, n + 1) + f(0, n + 2) \\ &\equiv \sum_{i=0}^{n} g(i, n) - \sum_{i=0}^{n} ig(i, n) - \sum_{i=0}^{n} (i + 1)g(i, n) \\ &\equiv 0 \pmod{2} \end{align*}$$

Lemma 2. If $\alpha$ and $\beta$ are integers such that $n! \mid \alpha \cdot (1! + 2! + \dots + (n-1)!) + \beta$ for all positive integer $n$, then $\alpha = \beta = 0$

Proof. We know that $1! + 2! + \dots + k! < (k+1)!$ for all positive integer $k$. Taking large enough $n$ for which $(n-1)! > |\beta|$ and $n > 2|\alpha| + 1$, we have
$$\begin{aligned} |\alpha \cdot (1! + 2! + \dots + (n-1)!)| + |\beta| &\le |\alpha| \cdot (1! + 2! + \dots + (n-1)!) + |\beta| \\ &< (2|\alpha| + 1) \cdot (n-1)! \\ &< n \cdot (n-1)! \\ &= n! \end{aligned}$$
But $n! \mid \alpha \cdot (1! + 2! + \dots + n!)+ \beta$, therefore $\alpha \cdot (1! + 2! + \dots + n!)+ \beta = 0$ for all large $n$. Thus, we can conclude that $\alpha = \beta = 0$, as desired. $\square$

Back to the problem. Let $m = k - 1$. The given sequence is equivalent to
$$a_0 + \sum_{j=1}^{n} j^m \cdot j!$$
$$a_n = \frac{a_0 + \sum_{j=1}^{n} j^m \cdot j!}{n!}.$$
We have $n! \mid a_0 + \sum_{j=1}^{n} j^m \cdot j!$ for all positive integer $n$. Now taking modulo $n!$ by using the expression of $x^m$ as mentioned before, we get
$$\begin{aligned} \sum_{j=1}^{n} j^m \cdot j! &= \sum_{j=1}^{n} j! \cdot \{f(0, m) + f(1, m)[(x+1)-1] + f(2, m)[(x+1)(x+2)-(x+1)] \\ &\quad + \dots + f(m, m)[(x+1)(x+2)\dots(x+m) - (x+1)(x+2)\dots(x+m-1)]\} \\ &= f(0, m) \cdot \sum_{i=1}^{n} i! + \sum_{i=1}^{n} \sum_{j=1}^{m} f(j, m) \cdot [(i+j)! - (i+j-1)!] \\ &= f(0, m) \cdot \sum_{i=1}^{n} i! + \sum_{j=1}^{m} \sum_{i=1}^{n} f(j, m) \cdot [(i+j)! - (i+j-1)!] \\ &= f(0, m) \cdot \sum_{i=1}^{n} i! + \sum_{j=1}^{m} f(j, m)[(n+j)! - j!] \\ &\equiv f(0, m) \cdot (1! + 2! + \dots + (n-1)!) - \sum_{j=1}^{m} f(j, m) \cdot j! \pmod{n!} \end{aligned}$$

Therefore, $n! \mid f(0, m) \cdot (1! + 2! + \dots + (n-1)!) + \beta$ for every positive integer $n$, when $\beta = a_0 - \sum_{j=1}^{m} f(j, m) \cdot j!$. Applying Lemma 2, we get $f(0, m) = 0$. And by Lemma 1, we get $3 \mid m-1$. Since $m = k-1$, therefore $k-2$ is divisible by 3, as desired.