Let $n$ be a positive integer which is not a square and consider a fundamental solution $(a,b)$ of Pell's equation
$$a^2-nb^2=1.$$
Setting
$$\begin{cases}
D=(a+1)^2b^2X^2+2(a+1)^2X+n,\\
P=b^4(a+1)X^2+2b^2(a+1)X+a,\\
Q=b^3X+b,
\end{cases}$$
we have the identity
$$P^2-DQ^2=1,$$
with $D(0)=n,P(0)=a$ and $Q(0)=b$. This explicitly answers the (first) question. A second post (below) shows that if $n$ is square-free and congruent to $3$ modulo $4$ then the degree of the polynomial $P$ is at most $2$.
In the rest of the post, we briefly sketch how the polynomials $P,Q$ and $D$ were constructed: let $P,Q,D\in\Bbb C[X]$ be three polynomials with
$$P^2-DQ^2=1$$
and $\deg(D)=2$. Here, we assume $\deg(P)=d>1$, so that $\deg(Q)=d-1$. Consider the polynomial $f=P^2$, so that $f'$ has degree $2d-1$. Setting $$P=u\prod_{i=1}^r(X-x_i)^{e_i}\quad\mbox{and}\quad Q=v\prod_{i=1}^s(X-y_i)^{f_i},$$
with $u,v\in\Bbb C,r\leq d$ and $s\leq d-1$, we obtain the factorization
$$f'=\prod_{i=1}^r(X-x_i)^{2e_i-1}\prod_{i=1}^r(X-y_i)^{2f_i-1}R,$$
with $R\in\Bbb C[X]$. Since $d=\sum_{i=1}^re_i=1+\sum_{i=1}^sf_i$, we find the identity
$$2d-1=\sum_{i=1}^r(2e_i-1)+\sum_{i=1}^s(2f_i-1)+\deg(R)=4d-2-r-s+\deg(R),$$
which leads to
$$r+s=2d-1+\deg(R).$$
It then follows that $r=d,s=d-1$ and $\deg(R)=0$, i.e. $P$ and $Q$ are separable. Remark that the polynomial $D$ is then itself separable. In this case, the cover $\Bbb P^1\to\Bbb P^1$ induced by $f$ is only ramified above $\infty,0$ and $1$, i.e. it is a Belyi map. The isomorphism classes of such covers are classified by Grothendieck's dessins d'enfants and, once we have fixed the integer $d$, there is a unique class with the above ramification data (totally ramified above $\infty$, all the points above $0$ have ramification index $2$ and the points above $1$ have ramification $2$ excepted two of them, which are unramified, corresponding to the roots of $D$). More precisely, if $T_d\in\Bbb Z[X]$ denotes the Chebyshev polynomial (of the first kind) of degree $d$, there exist constants $\lambda\in\Bbb C^\times$ and $\nu\in\Bbb C$, such that
$$f=\frac{T_{2d}(\lambda X+\nu)+1}2=T_d(\lambda X+\nu)^2.$$
This shows how to construct $P$. For example, in individ's answer, we find
$$P=T_2(\lambda X+\nu),$$
with $\lambda=\frac{\sqrt{2}}2$ and $\nu=\sqrt{2}$, while $\lambda=169i$ and $\nu=-99i$ (with $i^2=-1$) leads to Will Jagy's example for $n=29$.
We can then try to find a solution for general $n$ from the case $d=2$ in the above discussion. Consider a fundamental solution $(a,b)$ of the Pell's equation $a^2-nb^2=1$. It is clear that in Stefan Kohl's question, we can reduce to the case $k=0$.We have the identity $T_2=2X^2-1$ and we therefore set
$$P=2(\lambda X+\nu)^2-1.$$
The condition $P(0)=a$ leads to the relation $\nu=\frac12\sqrt{2a+2}$, while $P\in\Bbb Z[X]$ gives the identity $P=NX^2+MX+a$, with $N$ and $M$ integers such that $4(a+1)N=M^2$. We then find the factorization
$$P^2-1=\left(\frac14M^2X^2+M(a+1)X+nb^2\right)\left(\frac M{2(a+1)}X+1\right)^2.$$
Finally, setting $M=2(a+1)b^2$, we can factor $b^2$ on the first factor of the above identity and put it in the second factor, which leads to the result.
Added on Feb 17, 2015: A complete answer to the question can be found in this note.
Best Answer
This is a corrected version of my original response, incorporating a nice argument by Fedor Petrov.
Hua in his book (cf. review of MR0124306) proved that there are integers $s,K,N>0$ such that every $n>N$ with $n\equiv s\pmod{K}$ is a sum of $s$ $k$-th powers of primes. For any $t>0$ let $M(t)$ denote the set of residues modulo $K$ which can be represented by a sum of $t$ $k$-th powers of primes. Clearly $M(t+1)$ contains $M(t)+p^k$ for any prime $p$, hence $|M(t+1)|> |M(t)|$ unless $M(t+1)$ equals $M(t)+p^k$ for any prime $p$. In this case $M(t)$ is invariant under the shift of $p^k-q^k$ for any two distinct primes $p$ and $q$. The shifts are coprime (e.g. $p^k-q^k$ is coprime with $q$), hence $M(t)=M(t)+1$, and $M(t)$ contains all residues modulo $K$. This argument shows that $|M(K)|=K$, i.e. modulo $K$ every residue class is a sum of $K$ $k$-th powers of primes. If $p$ denotes the largest of the $K^2$ primes used in the latter representation, and $M$ equals $N+Kp^k$, then we have the following. For every $m>M$ there is a sum of $K$ $k$-th powers of primes, denote it by $m'$, such that $m-m'\equiv s\pmod{K}$ and $m-m'>N$. By Hua's theorem, $m-m'$ is a sum of $s$ $k$-th powers of primes, hence in fact every $m>M$ is a sum of $s+K$ $k$-th powers of primes.
To summarize: the statement in Fedor Petrov's original question follows from Hua's theorem.