Assuming $b_0\ne0$, a way to proceed is to introduce $A(x)=\sum\limits_{n=0}^{+\infty}a_nx^n$ and $B(x)=\sum\limits_{n=0}^kb_nx^n$ and to note that $A(x)B(x)$ has no power of $x$ of degree $\geqslant k$. Thus $A(x)=C(x)/B(x)$, where $C(x)$ is a polynomial of degree at most $k-1$ depending on $(b_n)_{0\leqslant n\leqslant k-1}$ and $(a_n)_{0\leqslant n\leqslant k-1}$.
The rest is as you describe it: decompose the rational function $C(x)/B(x)$ and collect the coefficients $a_n$ for $n\geqslant k$. For every root $1/r$ of $B$ with multiplicity $m$, the decomposition of $C(x)/B(x)$ includes terms $1/(1-rx)^s$ for $s\leqslant m$, and one uses the fact that
$$
\frac1{(1-rx)^s}=\sum_{n=0}^{+\infty}{n+s\choose s}r^nx^n,
$$
and that ${n+s\choose s}$ is a polynomial in $n$ with degree $s$ to conclude.
I will approach this from a more general perspective. Your specific question will be answered at the end of this post. Let $\lambda \in \mathbb{R}$ be a real parameter. The choice $\lambda = 0.069$ will correspond to your sequence. The general recurrence can be written as
$$
\begin{pmatrix} a_{n+1} \\ b_{n+1}
\end{pmatrix} = \begin{pmatrix}
1 & 0 \\ \lambda & 1
\end{pmatrix} \begin{pmatrix} a_{n+1} \\ b_n
\end{pmatrix} = \begin{pmatrix}
1 & 0 \\ \lambda & 1
\end{pmatrix} \begin{pmatrix}
1 & -\lambda \\ 0 & 1
\end{pmatrix}\begin{pmatrix} a_n \\ b_n
\end{pmatrix} = \begin{pmatrix}
1 & -\lambda \\ \lambda & 1-\lambda^2
\end{pmatrix} \begin{pmatrix} a_n \\ b_n
\end{pmatrix}.
$$
Define the $2\times 2$ matrix $$M_{\lambda} = \begin{pmatrix} 1 & -\lambda \\ \lambda & 1-\lambda^2 \end{pmatrix}.$$ Then starting from a given point $(a_0, b_0)$ we find $$\begin{pmatrix} a_n \\ b_n
\end{pmatrix} = M_{\lambda}^n \begin{pmatrix} a_0 \\ b_0
\end{pmatrix}.$$
Consider the quadratic polynomial $P_\lambda(x, y) = x^2+y^2 - \lambda\, x y$. A straightforward computation shows that this polynomial is invariant under the substitution
$$\begin{pmatrix} x \\ y \end{pmatrix} \leftarrow M_{\lambda} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} x - \lambda\,y \\ \lambda\,x+(1-\lambda^2)\,y \end{pmatrix}.
$$
This means that for all $n \in \mathbb{N}$ we have the equality $P_{\lambda}(a_n,b_n) = P_{\lambda}(a_0, b_0)$. In other words, all points $(a_n,b_n)$ lie on the same level set of $P_{\lambda}$. For $\lambda=0.069$ and starting point $(a_0, b_0) = (1, 10)$ this means that for all $n \in \mathbb{N}$ $$a_n^2+b_n^2 - 0.069 a_n b_n = 100.31.$$
In this case $P_{0.069}(x,y)=100.31$ defines an ellipse. For $\lambda=0$ a non-zero level set of $P_{\lambda}$ is a circle (though the sequence is stationary in this case so not very exciting). For $|\lambda|<2$ a level set is an ellipse, for $\lambda = \pm 2$ it is a pair of parallel lines and for $|\lambda|>2$ it is a hyperbola.
The recurrence relation has a nice solution in closed form. Take $\lambda \in (-2,2)$ so that the points follow an elliptical orbit. Let the parameter $s$ be such that $\sin(s) = \lambda/2$. Define
$$
\begin{eqnarray}
a_n &=& \cos(2 s \,n) \\
b_n &=& \sin(2 s \,n + s).
\end{eqnarray}
$$
One can verify that $a_n, b_n$ satisfy the recurrence relation for the parameter $\lambda$. Any solution of the recurrence with any starting point can be obtained from this fundamental solution by a change of phase and amplitude. See here for an approximation for $\lambda=0.069$ and $(a_0,b_0) = (1,10)$.
Best Answer
Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$ and sum over $n \ge 0$:
$$ \sum_{n \ge 0} (n + 1) a_{n + 2} z^n = \sum_{n \ge 0} w(n + 1) a_{n + 1} z^n - c \sum_{n \ge 0} a_{n + 1} z^n - \sum_{n \ge 0} z(n) a_n z^n $$
Recognize some sums: $\sum_{n \ge 0} a_{n + 2} z^n = \frac{A(z) - a_0 - a_1 z}{z^2}$, also $\sum_{n \ge 0} n a_n z^n = z \frac{d}{d z} A(z)$. As long as your $w(n)$ and $z(n)$ are polynomials, this will dispatch them. If they are powers of a constant, it gets hairier, but perhaps doable. The result will be a differential/functional equation for $A(z)$. From the function (even if it is a mess) a lot can be learned about the asymptotics of coefficients. A thorough treatment is by Flajolet and Sedgewick "Analytic Combinatorics".