We are going to find the general term of the sequence. Note that since $k > 1$, the characteristic polynomial $P(x) = x^2 - (k+1)x + 1$ has two different roots
$$r_1 = \frac{k+1+\sqrt{(k-1)(k+3)}}{2}, \quad r_2 = \frac{k+1-\sqrt{(k-1)(k+3)}}{2}.$$
So $a_n$ has a general form as
$$a_n = c_1 r_1^n + c_2 r_2^n,$$
where $c_1, c_2$ are fixed numbers. Considering the values of $a_1, a_2$, the values of $c_1, c_2$ are found
$$c_1 = \frac{\sqrt{k+3} - \sqrt{k-1}}{2\sqrt{k+3}}, \quad c_2 = \frac{\sqrt{k+3} + \sqrt{k-1}}{2\sqrt{k+3}}.$$
Lemma. The sequence has a general form as
$$a_n = \frac{\varphi^{2n-1} + \frac{1}{\varphi^{2n-1}}}{\varphi + \frac{1}{\varphi}},$$
$$\text{where } \varphi = \frac{\sqrt{k+3}+\sqrt{k-1}}{2}.$$
Proof. Note that $r_1 + r_2 = k+1$ and $r_1 r_2 = 1$. If we set $\varphi = \frac{\sqrt{k+3}+\sqrt{k-1}}{2}$, we have
$$\varphi^2 = \frac{k+1+\sqrt{(k-1)(k+3)}}{2} = r_1 = \frac{1}{r_2}, \\ \frac{1}{\varphi} = \frac{\sqrt{k+3}-\sqrt{k-1}}{2}, \\ \varphi + \frac{1}{\varphi} = \sqrt{k+3}.$$
Therefore
$$c_1 = \frac{1}{\varphi} \cdot \frac{1}{\varphi + \frac{1}{\varphi}}, \quad c_2 = \varphi \cdot \frac{1}{\varphi + \frac{1}{\varphi}}.$$
So we get
$$a_n = \frac{1}{\varphi(\varphi + \frac{1}{\varphi})} \cdot (\varphi^2)^n + \frac{\varphi}{\varphi + \frac{1}{\varphi}} \cdot \left(\frac{1}{\varphi^2}\right)^n = \frac{\varphi^{2n-1} + \frac{1}{\varphi^{2n-1}}}{\varphi + \frac{1}{\varphi}}.$$
It is easy to see, by induction, that if we consider the sequence modulo $k$ we have
$$(a_{6n+1}, a_{6n+2}, a_{6n+3}, a_{6n+4}, a_{6n+5}, a_{6n+6}) \stackrel{k}{\equiv} (1, 0, -1, -1, 0, 1).$$
Therefore another lemma is concluded.
Lemma. For any positive integer $n$, we have
$k \mid a_n \iff n \stackrel{3}{\equiv} 2, \text{ and } \gcd(k, a_n) = 1 \iff n \stackrel{3}{\not\equiv} 2.$
Now we prove the third and the final lemma.
Lemma. For any two odd numbers $m$ and $n$ such that $n \mid m$, we have
$$a_{\frac{n+1}{2}} \mid a_{\frac{m+1}{2}}$$
Proof. First, we claim that for any integer $n$, $\varphi^{2n} + \frac{1}{\varphi^{2n}} \in \mathbb{Z}^+$. For $n = 0, 1$ the claim is correct. Assume that the claim is true for $n-1, n-2$. We have
$$\underbrace{\left(\varphi^{2(n-2)} + \frac{1}{\varphi^{2(n-2)}}\right)}_{\in \mathbb{Z}^+} + \left(\varphi^{2n} + \frac{1}{\varphi^{2n}}\right) = \underbrace{\left(\varphi^{2(n-1)} + \frac{1}{\varphi^{2(n-1)}}\right)}_{\in \mathbb{Z}^+} \left(\varphi^2 + \frac{1}{\varphi^2}\right).$$
Therefore $\varphi^{2n} + \frac{1}{\varphi^{2n}} \in \mathbb{Z}^+$, so the claim is proved, using induction on $n$. Now set $m = nl$ (therefore $l$ is also odd). We have
$$a_{\frac{n+1}{2}} = \frac{\varphi^n + \frac{1}{\varphi^n}}{\varphi + \frac{1}{\varphi}}, \quad a_{\frac{m+1}{2}} = \frac{\varphi^{nl} + \frac{1}{\varphi^{nl}}}{\varphi + \frac{1}{\varphi}}.$$
Therefore
$$\begin{align*} \frac{a_{\frac{m+1}{2}}}{a_{\frac{n+1}{2}}} &= \frac{\varphi^{nl} + \frac{1}{\varphi^{nl}}}{\varphi^n + \frac{1}{\varphi^n}} \\ &= \varphi^{(l-1)n} - \varphi^{(l-3)n} + \dots - \frac{1}{\varphi^{(l-3)n}} + \frac{1}{\varphi^{(l-1)n}} \\ &= \sum_{i \stackrel{2}{\equiv} \frac{l-1}{2}} \left( \varphi^{2in} + \frac{1}{\varphi^{2in}} \right) - \sum_{j \stackrel{2}{\equiv} \frac{l-3}{2}} \left( \varphi^{2jn} + \frac{1}{\varphi^{2jn}} \right) = s \in \mathbb{Z}, \end{align*}$$
So $a_{\frac{m+1}{2}} = s \cdot a_{\frac{n+1}{2}}$, hence the lemma.

Back to the problem, let $n$ be an integer such that $a_n = k^m$ is a power of $k$. Assume that $n \ge 3$.
Consider a prime factor of $2n-1$ like $p$. Since both $p$ and $2n-1$ are odd numbers, according to the final lemma we have
$$a_{\frac{p+1}{2}} | a_n.$$
Again, consider a prime factor of $a_{\frac{p+1}{2}}$ like $q$, we have
$$q | a_{\frac{p+1}{2}} | a_n = k^m \implies q | k.$$
Therefore $\gcd(k, a_{\frac{p+1}{2}}) \ge q$. So according to the second lemma, since $\gcd(k, a_{\frac{p+1}{2}}) \ne 1$ we have
$$\frac{p+1}{2} \stackrel{3}{=} 2 \implies p \stackrel{3}{=} 0 \implies p = 3.$$
So $2n-1 = 3^v$ for some integer $v$. Since $n \ge 3$ we have $v \ge 2$. Therefore
$$9 | 3^v | 2n-1.$$
Again, according to the final lemma we obtain
$$a_5 = a_{\frac{9+1}{2}} | a_n.$$
But $a_5 = k(k^3 + 3k^2 - 3)$. So we must have $t = k^3 + 3k^2 - 3 \mid k^{m-1}$. Note that $k \ge 2$, so $t \ge 17$. Thus $m-1 > 0$. Let $r$ be a prime factor of $t$. We have
$$\left. \begin{array}{l} r \mid t \mid k^{m-1} \\ r \mid k^3 + 3k^2 - 3 \end{array} \right\} \implies r \mid 3 \implies r = 3.$$
Therefore $k^3 + 3k^3 - 3 = 3^h$, since $t \ge 17$ we have $h \ge 3$. The final equation implies $k = 3u$ for some integer $u$. So we can rewrite it as
$$27u^3 + 27u - 3 = 3^h.$$
Since $h \ge 3$, we have $27 \mid 3^h$ but $27 \nmid 27u^3 + 27u - 3$. Contradiction. This means our assumption that such $n \ge 3$ exists was incorrect. So $n=1, 2$ are the only answers of the problem. ■