This is a partial answer describing how to explicitly construct all polynomials $P,Q$ and $D$ satisfying a (polynomial) Pell's equation $P^2-DQ^2=1$ (as soon as $D$ has degree $2$). At the end of this post, we also come back to the original question in a special case.


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$. We will show that $P$ is closely related to Chebyshev polynomials.

Consider the 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.$$
This shows how to construct (the square of) $P$.

For example, in individ's answer, we find
$$P^2=\frac{T_4(\lambda X+\nu)}2,$$
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$.

Let now $n$ be an integer which is not a perfect square and 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$. Here, we only treat the case $n=2p$, where $p$ is an odd prime dividing $a-1$, which can be solved by setting $d=2$ in the above discussion. If $a-1=2mp$, the polynomials
$$D=b^2X^2+2(a+1)X+n,$$
$$P=mb^2X^2+2b^2X+a,\quad\mbox{and}\quad Q=bmX+b$$
satisfy the desired properties. As an example, for $n=46$, given the fundamental solution $a=24335$ and $b=3588$ we find
$$\begin{cases}
D=12873744X^2+48672X+46,\\
P=6810210576X^2+25747488X+24335,\\
Q=1898052X+3588.
\end{cases}$$