The sequence can be any constant sequence $p, p, p, \dots$ where $p$ is a prime.

The recurrence relation can be rewritten as
$$p_{n+2} + k = (p_{n+1} + k) + (p_n + k).$$
Since the characteristic equation $\lambda^2 - \lambda - 1 = 0$ has roots $\frac{1 \pm \sqrt{5}}{2}$, we have
$$p_n = A \left( \frac{1 + \sqrt{5}}{2} \right)^n + B \left( \frac{1 - \sqrt{5}}{2} \right)^n - k,$$
for some constants $A, B$.

Furthermore, as there are at most $p_1^2$ possibilities for the remainders of the pair $(p_{n+1}, p_n)$ modulo $p_1$, and the remainders of the subsequent terms are uniquely determined by these, the sequence must be periodic modulo $p_1$. Thus, there are infinitely many terms which are congruent to $p_1$ modulo $p_1$. Since they are primes, they must be $p_1$.
If $A \neq 0$, the term $\left(\frac{1+\sqrt{5}}{2}\right)^n$ dominates the expression for $p_n$, and so the sequence is eventually strictly increasing (if $A > 0$) or decreasing (if $A < 0$). This contradicts our observation. Thus, we must have $A = 0$. Similarly, if $B \neq 0$, the term $\left(\frac{1-\sqrt{5}}{2}\right)^n$ now dominates the expression for $p_n$, which again implies $p_n \neq p_1$ for all sufficiently large $n$. Thus, we must have $B = 0$. It follows that $p_n = -k$ is a constant.
Conversely, if the sequence is $p, p, p, \dots$, where $p$ is a prime, we can take $k = -p$ so that the recurrence relation holds.