Here are some results concerning the degree of the polynomial $P$. We only treat the cases where $n$ is a positive, square-free integer congruent to $3$ modulo $4$, showing that the degree of $P$ is less than or equal to $2$.

We start by the weaker assumption that, given the positive integer $n$ and a solution $(a,b)$ of Pell's equation $a^2-nb^2$, there exist polynomials $D,P,Q\in\Bbb Q[X]$ and a rational number $k$ such that $P^2-DQ^2=1$, with $D(k)=n,P(k)=a$ and $Q(k)=b$. Let $d$ be the degree of $P$. As mentioned in my other post, and following the conventions and results in David Speyer's answer, there exist constants $\alpha\in\Bbb C$ and $\beta,\gamma\in\Bbb Q$, with $\alpha^2,\gamma^2\in\Bbb Q$ such that $$\begin{cases} P=\pm T_d\left(\alpha(X+\beta)\right),\\ Q=\gamma U_{d-1}\left(\alpha(X+\beta)\right),\\ D=\gamma^{-2}\left(\alpha^2(X+\beta)^2-1\right), \end{cases}$$ where $T_d$ (resp. $U_d$) denotes the degree $d$ Chebyshev polynomial of the first kind (resp. of the second kind). From the hypothesis on $P$, we can assume $\beta=0$. We have the identity $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X+\sqrt{X^2-1}\right)^d,$$ which leads to $$P+Q\sqrt{D}=\left(\alpha X+\sqrt{\alpha^2X^2-1}\right)^d.$$ If $d$ is odd then the explicit expression of $T_d$ shows that $\alpha$ (and therefore $\gamma$) is rational. Evaluating at $k$, we then obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^d,$$ with $u,v\in\Bbb Q$. It then follows that $u+v\sqrt{n}$ is a unit in the ring of integers of $\Bbb Q(\sqrt{n})$ and, since we are assuming $n\equiv3\pmod4$, the elements $u$ and $v$ are integers. In particular, for $d>1$, the couple $(a,b)$ cannot be a fundamental solution of Pell's equation.

From now on, we assume $d=2m$ even. For $\alpha\in\Bbb Q$, we proceed as above and deduce that $(a,b)$ cannot be a fundamental solution for $d>1$. Suppose then that $\alpha=\sqrt{w}$, we $w\in\Bbb Q$ not a square, so that $\gamma=t\alpha$, with $t\in\Bbb Q$. We have the relation $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X^2-1+2X\sqrt{X^2-1}\right)^m$$ and thus $$P+Q\sqrt{D}=\left(\alpha^2X^2-1+2\alpha\sqrt{\alpha^2X^2-1}\right)^m.$$ Evaluating at $k$, we then easily obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^m,$$ with $u,v\in\Bbb Q$. Once again, for $m>1$, it then follows that the couple $(a,b)$ cannot be a fundamental solution, leading to the result.

A final remark: for general $n$, if $(a,b)$ is a fundamental solution then $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^r,$$ where $u+v\sqrt{n}$ is a fundamental unit of $\Bbb Q(\sqrt{n})$. For example, in Stefan Kohl's example for $n=13$, we have $$649+180\sqrt{13}=\left(\frac{11}2+\frac32\sqrt{13}\right)^3.$$ I'm definitely not an expert on this subject, but the above discussion combined with an explicit bound for the integer $r$ would lead to a bound for the degree of $P$ and therefore give a complete answer to the second question.

Here are some results concerning the degree of the polynomial $P$. We only treat the cases where $n$ is a positive, square-free integer congruent to $3$ modulo $4$, showing that the degree of $P$ is less than or equal to $2$.

We start by the weaker assumption that, given the positive integer $n$ and a solution $(a,b)$ of Pell's equation $a^2-nb^2=1$, there exist polynomials $D,P,Q\in\Bbb Q[X]$ and a rational number $k$ such that $P^2-DQ^2=1$, with $D(k)=n,P(k)=a$ and $Q(k)=b$. Let $d$ be the degree of $P$. As mentioned in my other post, and following the conventions and results in David Speyer's answer, there exist constants $\alpha\in\Bbb C$ and $\beta,\gamma\in\Bbb Q$, with $\alpha^2,\gamma^2\in\Bbb Q$ such that $$\begin{cases} P=\pm T_d\left(\alpha(X+\beta)\right),\\ Q=\gamma U_{d-1}\left(\alpha(X+\beta)\right),\\ D=\gamma^{-2}\left(\alpha^2(X+\beta)^2-1\right), \end{cases}$$ where $T_d$ (resp. $U_d$) denotes the degree $d$ Chebyshev polynomial of the first kind (resp. of the second kind). From the hypothesis on $P$, we can assume $\beta=0$. We have the identity $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X+\sqrt{X^2-1}\right)^d,$$ which leads to $$P+Q\sqrt{D}=\left(\alpha X+\sqrt{\alpha^2X^2-1}\right)^d.$$ If $d$ is odd then the explicit expression of $T_d$ shows that $\alpha$ (and therefore $\gamma$) is rational. Evaluating at $k$, we then obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^d,$$ with $u,v\in\Bbb Q$. It then follows that $u+v\sqrt{n}$ is a unit in the ring of integers of $\Bbb Q(\sqrt{n})$ and, since we are assuming $n\equiv3\pmod4$, the elements $u$ and $v$ are integers. In particular, for $d>1$, the couple $(a,b)$ cannot be a fundamental solution of Pell's equation.

From now on, we assume $d=2m$ even. For $\alpha\in\Bbb Q$, we proceed as above and deduce that $(a,b)$ cannot be a fundamental solution for $d>1$. Suppose then that $\alpha=\sqrt{w}$, we $w\in\Bbb Q$ not a square, so that $\gamma=t\alpha$, with $t\in\Bbb Q$. We have the relation $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X^2-1+2X\sqrt{X^2-1}\right)^m$$ and thus $$P+Q\sqrt{D}=\left(\alpha^2X^2-1+2\alpha\sqrt{\alpha^2X^2-1}\right)^m.$$ Evaluating at $k$, we then easily obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^m,$$ with $u,v\in\Bbb Q$. Once again, for $m>1$, it then follows that the couple $(a,b)$ cannot be a fundamental solution, leading to the result.

A final remark: for general $n$, if $(a,b)$ is a fundamental solution then $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^r,$$ where $u+v\sqrt{n}$ is a fundamental unit of $\Bbb Q(\sqrt{n})$. For example, in Stefan Kohl's example for $n=13$, we have $$649+180\sqrt{13}=\left(\frac{11}2+\frac32\sqrt{13}\right)^3.$$ I'm definitely not an expert on this subject, but the above discussion combined with an explicit bound for the integer $r$ would lead to a bound for the degree of $P$ and therefore give a complete answer to the second question.

Here are some results concerning the degree of the polynomial $P$. We only treat the cases where $n$ is a positive, square-free integer congruent to $3$ modulo $4$, showing that the degree of $P$ is less than or equal to $2$.

We start by the weaker assumption that, given the positive integer $n$ and a solution $(a,b)$ of Pell's equation $a^2-nb^2$ there exist polynomials $D,P,Q\in\Bbb Q[X]$ and a rational number $k$ such that $P^2-DQ^2=1$, with $D(k)=n,P(k)=a$ and $Q(k)=b$. Let $d$ be the degree of $P$. As mentioned in my other post, and following the conventions and results in David Speyer's answer, there exist constants $\alpha\in\Bbb C$ and $\beta,\gamma\in\Bbb Q$, with $\alpha^2,\gamma^2\in\Bbb Q$ such that $$\begin{cases} P=\pm T_d\left(\alpha(X+\beta)\right),\\ Q=\gamma U_{d-1}\left(\alpha(X+\beta)\right),\\ D=\gamma^{-2}\left(\alpha^2(X+\beta)^2-1\right), \end{cases}$$ where $T_d$ (resp. $U_d$) denotes the degree $d$ Chebyshev polynomial of the first kind (resp. of the second kind). From the hypothesis on $P$, we can assume $\beta=0$. We have the identity $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X+\sqrt{X^2-1}\right)^d,$$ which leads to $$P+Q\sqrt{D}=\left(\alpha X+\sqrt{\alpha^2X^2-1}\right)^d.$$ If $d$ is odd then the explicit expression of $T_d$ shows that $\alpha$ (and therefore $\gamma$) is rational. Evaluating at $k$, we then obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^d,$$ with $u,v\in\Bbb Q$. It then follows that $u+v\sqrt{n}$ is a unit in the ring of integers of $\Bbb Q(\sqrt{n})$ and, since we are assuming $n\equiv3\pmod4$, the elements $u$ and $v$ are integers. In particular, for $d>1$, the couple $(a,b)$ cannot be a fundamental solution of Pell's equation.

From now on, we assume $d=2m$ even. For $\alpha\in\Bbb Q$, we proceed as above and deduce that $(a,b)$ cannot be a fundamental solution for $d>1$. Suppose then that $\alpha=\sqrt{w}$, we $w\in\Bbb Q$ not a square, so that $\gamma=t\alpha$, with $t\in\Bbb Q$. We have the relation $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X^2-1+2X\sqrt{X^2-1}\right)^m$$ and thus $$P+Q\sqrt{D}=\left(\alpha^2X^2-1+2\alpha\sqrt{\alpha^2X^2-1}\right)^m.$$ Evaluating at $k$, we then easily obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^m,$$ with $u,v\in\Bbb Q$. Once again, for $m>1$, it then follows that the couple $(a,b)$ cannot be a fundamental solution, leading to the result.

A final remark: for general $n$, if $(a,b)$ is a fundamental solution then $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^r,$$ where $u+v\sqrt{n}$ is a fundamental unit of $\Bbb Q(\sqrt{n})$. For example, in Stefan Kohl's example for $n=13$, we have $$649+180\sqrt{13}=\left(\frac{11}2+\frac32\sqrt{13}\right)^3.$$ I'm definitely not an expert on this subject, but the above discussion combined with an explicit bound for the integer $r$ would lead to a bound for the degree of $P$ and therefore give a complete answer to the second question.

Here are some results concerning the degree of the polynomial $P$. We only treat the cases where $n$ is a positive, square-free integer congruent to $3$ modulo $4$, showing that the degree of $P$ is less than or equal to $2$.

We start by the weaker assumption that, given the positive integer $n$ and a solution $(a,b)$ of Pell's equation $a^2-nb^2$, there exist polynomials $D,P,Q\in\Bbb Q[X]$ and a rational number $k$ such that $P^2-DQ^2=1$, with $D(k)=n,P(k)=a$ and $Q(k)=b$. Let $d$ be the degree of $P$. As mentioned in my other post, and following the conventions and results in David Speyer's answer, there exist constants $\alpha\in\Bbb C$ and $\beta,\gamma\in\Bbb Q$, with $\alpha^2,\gamma^2\in\Bbb Q$ such that $$\begin{cases} P=\pm T_d\left(\alpha(X+\beta)\right),\\ Q=\gamma U_{d-1}\left(\alpha(X+\beta)\right),\\ D=\gamma^{-2}\left(\alpha^2(X+\beta)^2-1\right), \end{cases}$$ where $T_d$ (resp. $U_d$) denotes the degree $d$ Chebyshev polynomial of the first kind (resp. of the second kind). From the hypothesis on $P$, we can assume $\beta=0$. We have the identity $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X+\sqrt{X^2-1}\right)^d,$$ which leads to $$P+Q\sqrt{D}=\left(\alpha X+\sqrt{\alpha^2X^2-1}\right)^d.$$ If $d$ is odd then the explicit expression of $T_d$ shows that $\alpha$ (and therefore $\gamma$) is rational. Evaluating at $k$, we then obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^d,$$ with $u,v\in\Bbb Q$. It then follows that $u+v\sqrt{n}$ is a unit in the ring of integers of $\Bbb Q(\sqrt{n})$ and, since we are assuming $n\equiv3\pmod4$, the elements $u$ and $v$ are integers. In particular, for $d>1$, the couple $(a,b)$ cannot be a fundamental solution of Pell's equation.

From now on, we assume $d=2m$ even. For $\alpha\in\Bbb Q$, we proceed as above and deduce that $(a,b)$ cannot be a fundamental solution for $d>1$. Suppose then that $\alpha=\sqrt{w}$, we $w\in\Bbb Q$ not a square, so that $\gamma=t\alpha$, with $t\in\Bbb Q$. We have the relation $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X^2-1+2X\sqrt{X^2-1}\right)^m$$ and thus $$P+Q\sqrt{D}=\left(\alpha^2X^2-1+2\alpha\sqrt{\alpha^2X^2-1}\right)^m.$$ Evaluating at $k$, we then easily obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^m,$$ with $u,v\in\Bbb Q$. Once again, for $m>1$, it then follows that the couple $(a,b)$ cannot be a fundamental solution, leading to the result.

A final remark: for general $n$, if $(a,b)$ is a fundamental solution then $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^r,$$ where $u+v\sqrt{n}$ is a fundamental unit of $\Bbb Q(\sqrt{n})$. For example, in Stefan Kohl's example for $n=13$, we have $$649+180\sqrt{13}=\left(\frac{11}2+\frac32\sqrt{13}\right)^3.$$ I'm definitely not an expert on this subject, but the above discussion combined with an explicit bound for the integer $r$ would lead to a bound for the degree of $P$ and therefore give a complete answer to the second question.