Rewrite the equation as $\frac{n(a_{n+2}-a_{n+1})}{a_n} = k$. If $a_n$ is a polynomial in $n$, say $a_n = r(n) = \sum_{i=0}^{d} r_i n^i$, then the limit $\lim_{n \to \infty} \frac{n(a_{n+2}-a_{n+1})}{a_n}$ must exist and be equal to $k$. But
$$\begin{align*} & \lim_{n \to \infty} \frac{n(a_{n+2} - a_{n+1})}{a_n} \\ &= \lim_{n \to \infty} \frac{n \left( \sum_{i=0}^{d} r_i (n+2)^i - \sum_{i=0}^{d} r_i (n+1)^i \right)}{\sum_{i=0}^{d} r_i n^i} \\ &= \lim_{n \to \infty} \frac{n \sum_{i=0}^{d} r_i ((n+2)^i - (n+1)^i)}{\sum_{i=0}^{d} r_i n^i} \\ &= \lim_{n \to \infty} \frac{n \sum_{i=0}^{d} r_i ((n+2)^{i-1} + (n+2)^{i-2}(n+1) + \dots + (n+1)^{i-1})}{\sum_{i=0}^{d} r_i n^i} \\ &= \lim_{n \to \infty} \frac{n^d \sum_{i=0}^{d} r_i n^{i-d} \left( \left(1+\frac{2}{n}\right)^{i-1} + \left(1+\frac{2}{n}\right)^{i-2} \left(1+\frac{1}{n}\right) + \dots + \left(1+\frac{1}{n}\right)^{i-1} \right)}{n^d \sum_{i=0}^{d} r_i n^{i-d}} \\ &= \lim_{n \to \infty} \frac{r_d \left( \left(1+\frac{2}{n}\right)^{d-1} + \left(1+\frac{2}{n}\right)^{d-2} \left(1+\frac{1}{n}\right) + \dots + \left(1+\frac{1}{n}\right)^{d-1} \right)}{r_d} = d \end{align*}$$
So if $a_n$ is a polynomial in $n$ then $k$ is the degree of $a_n$ and is a nonnegative integer.

Now we need to show an example of polynomial $r_k(n)$ for each nonnegative integer $k$. For $k = 0$ and $k = 1$, one may consider $r_0(n) = 0$ and $r_1(n) = n$. For $k \ge 2$, let's find a polynomial
$$r(n) = n^k + r_{k-1} n^{k-1} + \cdots + r_1 n + r_0$$
such that $n(r(n+2) - r(n+1)) = kr(n)$ for all $n$.
Expanding $(n + 2)^i$ and $(n + 1)^i$ via binomial theorem, we obtain the system of equations
$$\begin{align*} & 3 \binom{k}{k-2} + \binom{k-1}{k-2} r_{k-1} = k r_{k-1} \\ & 7 \binom{k}{k-3} + 3 \binom{k-1}{k-3} r_{k-1} + \binom{k-2}{k-3} r_{k-2} = k r_{k-2} \\ & \qquad \dots \\ & (2^j - 1) \binom{k}{k-j} + (2^{j-1} - 1) \binom{k-1}{k-j} r_{k-1} + \dots + \binom{k-j+1}{k-j} r_{k-j+1} = k r_{k-j+1} \\ & \qquad \dots \end{align*}$$
Since $\binom{k-j+1}{k-j} = k-j+1 \neq k$ it is possible to find $r_{k-j+1}$ in each equation and the system is possible, so there is such a polynomial.

For the second part, rewrite the given equation as $n\left(\frac{a_{n+2}}{a_{n+1}} - 1\right) = k \frac{a_n}{a_{n+1}}$. If there exists polynomials $p$ and $q$ such that $\frac{a_{n+1}}{a_n} = \frac{p(n)}{q(n)}$, then
$$n \left( \frac{p(n+1)}{q(n+1)} - 1 \right) = k \frac{q(n)}{p(n)} \iff n(p(n+1) - q(n+1))p(n) = kq(n+1)q(n)$$
We may suppose without loss of generality that $p(n)$ and $q(n)$ don't have common factors. Let $m$ and $m'$ be the degrees of $p$ and $q$, respectively. If $m = m'$ then the right hand side has degree $2m$ and the degree of $p(n+1) - q(n+1)$ is $m-1$. This means that the leading coefficients of $p$ and $q$ are equal. Since $p(n)$ and $q(n)$ don't have common factors, $p(n)$ divides $q(n+1)$, which in this case means $p(n) = q(n+1)$. Substituting yields $n(q(n+2) - q(n+1)) = kq(n)$, and $q$ satisfies the first part of the problem, and thus $k$ must be a nonnegative integer.

If $m \neq m'$ by checking degrees we must have $1 + \max(m, m') + m = 2m' \Rightarrow 2m' \le 1 + m + m' \iff m < m' \Rightarrow 1 + m' + m = 2m' \iff m' = m + 1$. The polynomials $q(n+1)$ and $p(n+1) - q(n+1)$ don't have common factors, so $q(n)$ divides $p(n+1) - q(n+1)$. These two polynomials have both degree $m'$ and opposite leading coefficients, so $p(n+1) = q(n+1) - q(n)$. Substituting yields the polynomial identity $n(q(n) - q(n-1)) = -kq(n+1)$. Now if $r(n) = q(1-n)$ and $m = -n$ then $n(r(m+2) - r(m+1)) = -kr(m)$ and we reduce the problem to the first part again for $-k$ instead of $k$. So, in this case, $k$ must be a nonpositive integer.

Conversely, it's not hard to obtain $p(n)$ and $q(n)$ from the above case, so the answer for the second part is $k$ integer.