YES, define $a_k$ by $a_0=0$, $a_k=a_{-k}$ for $k<0$ and for $k>0$ $a_k=m!$ where $m\ge 1$ is as large as possible subject to $k$ being a multiple of $m!$. Then $$a_{k+m!} \equiv a_k \mod m.$$ However we have $a_j=a_{m\cdot m!+j}$ for $1 \le j\le m!-1$ but not for $j=m!$ when $a_{m!} \ne a_{(m+1)!}$ so the sequence can't satisfy a recurrence of finite order.

By request: Here it is from $a_{-9}$ to $a_{33}:$ $${\small \cdots 1,2,1,6,1,2,1,2,1,}\mathbf{0}\small{,\overline{1,2,1,2,1,6,1,2,1,2,1,6,1,2,1,2,1,6,1,2,1,2,1,24},1,2,1,2,1,6,1,\cdots}$$ $a_0=\mathbf{0}$ and all other terms are positive. The length 24 sequence with the overline keeps repeating except the $4!=24$ is $5!=120$ in positions 120,240,360,480,600 (but not 720) 840,960

Three notes:

• One could use the least common multiple of $\lbrace1,2,3\cdots m\rbrace$ in place of $m!$
• Since the question asked only about primes one could make it have period #$p$ (p primorial) $\mod p$
• If $a_k$ satisfies a recurrence of order $n$ mod $m$ then it is periodic $\mod m$ with a period $P=P_m$ which is no greater than $m^n$. Hence it is enough to ask: " If $<a_k>$ is an integer sequence which is periodic mod $m$ (with a period $P_m$ depending on $m$) for every $m$, must it satisfy a finite recurrence?
7 added 735 characters in body

YES, define $a_k$ by $a_0=0$, $a_k=a_{-k}$ for $k<0$ and for $k>0$ $a_k=m!$ where $m\ge 1$ is as large as possible subject to $k$ being a multiple of $m!$. Then $$a_{k+m!} \equiv a_k \mod m.$$ However we have $a_j=a_{m\cdot m!+j}$ for $1 \le j\le m!-1$ but not for $j=m!$ when $a_{m!} \ne a_{(m+1)!}$ so the sequence can't satisfy a recurrence of finite order.

By request: Here it is from $a_{-9}$ to $a_{33}:$ $${\small \cdots 1,2,1,6,1,2,1,2,1,}\mathbf{0}\small{,\overline{1,2,1,2,1,6,1,2,1,2,1,6,1,2,1,2,1,6,1,2,1,2,1,24},1,2,1,2,1,6,1,\cdots}$$ $a_0=\mathbf{0}$ and all other terms are positive. The length 24 sequence with the overline keeps repeating except the $4!=24$ is $5!=120$ in positions 120,240,360,480,600 (but not 720) 840,960

Three notes:

• One could use the least common multiple of $\lbrace1,2,3\cdots m\rbrace$ in place of $m!$
• Since the question asked only about primes one could make it have period #$p$ (p primorial) $\mod p$
• If $a_k$ satisfies a recurrence of order $n$ mod $m$ then it is periodic $\mod m$ with a period no greater than $m^n$.
6 added 5 characters in body

Define

YES, define $a_k$ by $a_0=0$, $a_k=a_{-k}$ for $k<0$ and for $k>0$ $a_k=m!$ where $m\ge 1$ is as large as possible subject to $k$ being a multiple of $m!$. Then $$a_{k+m!} \equiv a_k \mod m.$$ However we have $a_j=a_{m\cdot m!+j}$ for $1 \le j\le m!-1$ but not for $j=m!$ when $a_{m!} \ne a_{(m+1)!}$ so the sequence can't satisfy a recurrence of finite order.

5 added 1 characters in body
4 added 63 characters in body; edited body
3 deleted 1345 characters in body
2 edited body
1