In any general recurrence of the form:
$$x_n = \sum_{i=1}^k {a_i x_{n-i}}$$
you can determine an explicit formula in terms of the roots of the polynomial of degree k:
$$z^k - a_1{z^{k-1}} - a_2{z^{k-2}} - a_{k-1}z - a_k$$
If the polynomial has no repeated roots, then the form of the explicit formula will be:
$$x_n = b_1 r_1^n + b_2 r_2^n + ... + b_k r_k^n$$
Where the $b_i$ can be any numbers, and the $r_i$ are the distinct roots of the polynomial.
This means that "most of the time," $\lim\limits_{n\to \infty}{x_{n+1}/x_n}$ will be equal to the root $r_i$ with the largest absolute value such that $b_i\neq 0$. If two $r_i$ have the same largest absolute value, the convergent behavior might be odd - it possibly might never converge.
There is a lot of linear algebra involved in this - the $r_i$s are eigenvalues of a matrix which sends $(x_i,x_{i+1},...,x_{i+k-1})$ to $(x_{i+1},...,x_{i+k})$
In the case of what you call the k-nacci numbers, your polynomial is:
$$x^k-x^{k-1}-x^{k-2}-..-1 = x^k -\frac{x^k-1}{x-1}$$
I'm not sure what you can say about the roots of this polynomial when $k>2$. It's easy to show it has no repeated roots (a polynomial has no repeated roots of it is relatively prime to its derivative.)
Step 1. Since, by the Binet formula,
$$ F_n = \frac{1}{\sqrt{5}}\left(\sigma^n-\bar{\sigma}^n\right), $$
where $\sigma+\bar{\sigma}=1$ and $\sigma\bar{\sigma}=-1$, we have:
$$ F_m \mid F_{mn}, $$
since in $\mathbb{Z}[x,y]$ the polynomial $x^m-y^m$ divides the polynomial $x^{mn}-y^{mn}$.
Step 2. We can prove our statement by assuming without loss of generality that $k$ is a prime power. The Chinese theorem in conjunction with Step 1 grants that if the statement holds when $k$ is a prime power, then it holds for every integer.
Step 3. The Pisano period for the Fibonacci and Lucas sequences $\!\!\pmod{2}$ is $3$. In particular, $F_n$ (as well as $L_n$) is even iff $n$ is a multiple of $3$. Moreover,
$$ F_{2n} = F_n \cdot L_n.$$
Step 4. By assuming that $2^h\mid F_n$ we have $n=3m$ in virtue of Step 3, and:
$$ F_{2^{(d-1)h}n} = F_{2^{(d-1)h}3m} = F_{2^{(d-1)h-1}3m}L_{2^{(d-1)h-1}3m} = F_{3m}\cdot\prod_{j=0}^{(d-1)h-1}L_{3\cdot 2^j m}, $$
so:
$$ \nu_2(F_{2^{(d-1)h}n})\geq \nu_2(F_{n}) + (d-1)h \geq dh,$$
since every term in the product is even. So we just proved the statement in case that $k$ is a power of $2$.
Step 5. We assume now that $k$ is odd. Since $\frac{x^l-y^l}{x-y}=\sum_{j=0}^{l-1} x^j y^{l-1-j}$, we have:
$$\frac{F_{kn}}{F_n}=\sum_{j=0}^{k-1} \sigma^{jn}\bar{\sigma}^{(k-1-j)n}=(-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}} (-1)^{jn} L_{(k-1-2j)n},$$
where $L_a = \sigma^a + \bar{\sigma}^a$. If now we use the identity:
$$ L_{2a} = \sigma^{2a}+\bar{\sigma}^{2a} = 5 F_a^2 + 2(-1)^a$$
we get:
$$\frac{F_{kn}}{F_n}= (-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}} (-1)^{jn}\left(5 F_{\left(\frac{k-1}{2}-j\right)n}^2+2(-1)^{\left(\frac{k-1}{2}-j\right)n}\right).$$
Since $F_n$ divides $F_{mn}$ and $k$ divides $F_{n}$, the last sum $\pmod{k}$ is just:
$$ \frac{F_{kn}}{F_n}\equiv (-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}}2(-1)^{\frac{k-1}{2}n}\equiv k (-1)^{\frac{k-1}{2}n}\equiv 0\pmod{k}.$$
Hence we have that $k\mid F_n$ implies $(k F_n)\mid F_{kn}$, and our claim follows by induction.
Best Answer
Yes. Consider any prime $p$. (Actually we don't need $p$ to be prime; consider any nonzero number $p$.)
You can of course take $F_0 = 0$ which is divisible by $p$, but let's suppose you want some $n > 1$ such that $F_n$ is divisible by $p$. Consider the Fibonacci sequence modulo $p$; call it $F'$.
That is, you have $F'_0 = 0$, $F'_1 = 1$, and for $n \ge 0$, you have $F'_{n+2} \equiv F'_{n+1} + F'_n \mod p$.
Now, there are only $p^2$ possible pairs of remainders $(F'_k, F'_{k+1})$, so some pair of consecutive remainders must occur again at some point. Further, the future of the sequence is entirely determined by its value at some two consecutive indices, so the sequence must itself repeat after that point. And it cannot go into some cycle that does not include $(F'_0, F'_1)$, because we can also work the sequence backwards: we can find $F'_{k-1}$ using $F'_{k-1} \equiv F'_{k+1} - F'_{k} \mod p$, etc.
This means that there always exists some $n > 0$ such that $F'_n \equiv F_0 \equiv 0 \mod p$ and $F'_{n+1} \equiv F_1 \equiv 1 \mod p$. Such an $n$ will do. This is called the period of the sequence modulo $p$ (or the $p$th Pisano period; of course some smaller $n$ may also exist (for which $F'_{n+1} \not\equiv 1 \mod p$).