Given a positive integer $n$ which is not a perfect square, it is well-known that
[Pell's equation][1] $a^2 - nb^2 = 1$ is always solvable in non-zero integers $a$ and $b$.

> <b>Question:</b> Let $n$ be a positive integer which is not a perfect square.
> Is there always a polynomial $D \in \mathbb{Z}[x]$ of degree $2$, an integer $k$ and
> nonzero polynomials $P, Q \in \mathbb{Z}[x]$ such that $D(k) = n$ and $P^2 - DQ^2 = 1$,
> where $a = P(k)$, $b = Q(k)$ is the fundamental solution of the equation
> $a^2 - nb^2 = 1$?
>
> If yes, is there an upper bound on the degree of the polynomials $P$ and $Q$ --
> and if so, is it even true that the degree of $P$ is always $\leq 6$?

<b>Example:</b> Consider $n := 13$.
Putting $D_1 := 4x^2+4x+5$ and $D_2 := 25x^2-14x+2$, we have $D_1(1) = D_2(1) = 13$.
Now the fundamental solutions of the equations
$P_1^2 - D_1Q_1^2 = 1$ and $P_2^2 - D_2Q_2^2 = 1$ are given by

  - $P_1 := 32x^6+96x^5+168x^4+176x^3+120x^2+48x+9$, 

  - $Q_1 := 16x^5+40x^4+56x^3+44x^2+20x+4$

and

  - $P_2 := 1250x^2-700x+99$, 

  - $Q_2 := 250x-70$,

respectively. Therefore $n = 13$ belongs to at least $2$ different series whose solutions
have ${\rm deg}(P) = 6$ and ${\rm deg}(P) = 2$, respectively.

Examples for all non-square $n \leq 150$ can be found [here][2].

<b>Added on Feb 3, 2015:</b> All what remains to be done in order to turn
Leonardo's answers into a complete answer to the question is to find out which values
the index of the group of units of $\mathbb{Z}[\sqrt{n}]$ in the group of units
of the ring of integers of the quadratic field $\mathbb{Q}(\sqrt{n})$
can take. This part is presumably not even really MO level, but it's just
not my field -- maybe someone knows the answer?

<b>Added on Feb 14, 2015:</b> As nobody has completed the answer so far, it seems
this may be less easy than I thought on a first glance. 

<b>Added on Feb 17, 2015:</b> Leonardo Zapponi has given now a complete answer to
the question in [this note][3].

  [1]: http://en.wikipedia.org/wiki/Pell%27s_equation
  [2]: https://stefan-kohl.github.io/problems/pellpolynomials.txt
  [3]: http://arxiv.org/pdf/1503.00637v1