We can completely classify modulo which $n$ there is a surjective sequence. Indeed, I claim that $\text{fib}_{n, x_0, x_1}$ is surjective for some seed values $x_0,x_1$ iff the usual Fibonacci sequence $F_k$ is surjective modulo $n$. As stated on [OEIS](http://oeis.org/A079002), this happens precisely when $n$ is of one of the forms $5^k,2\cdot 5^k,4\cdot 5^k,3^j\cdot 5^k,6\cdot 5^k,7\cdot 5^k,14\cdot 5^k$.

One implication is obvious. For the other, assume $\text{fib}_{n, x_0, x_1}$ is surjective modulo $n$. In particular we have $\text{fib}_{n, x_0, x_1}(k)\equiv 0\pmod n$. Shifting the index we may assume $k=0$, i.e. $x_0=0$. But then we have $\text{fib}_{n, x_0, x_1}(k)\equiv x_1F_k\pmod n$. This sequence is surjective modulo $n$ iff $F_k$ is and $x_1$ is coprime to $n$.

----------
Old answer:

Not necessarily. Let $F_k$ be the regular Fibonacci sequence. Then we have $\text{fib}_{n, x_0, x_1}(k)=x_0F_{k+1}+(x_1-x_0)F_k\mod n$. Letting $\pi(n)$ be the $n$th [Pisano period](https://en.wikipedia.org/wiki/Pisano_period), this implies that $\text{fib}_{n, x_0, x_1}$ is periodic with period dividing $\pi(n)$. There are plenty of numbers for which $\pi(n)<n$, for instance all numbers modulo which $x^2-x-1$ has a root (as by Binet's formula and Euler's theorem we then have $\pi(n)\mid\varphi(n)<n$). For such $n$ the sequence cannot be surjective.