First a solution that I wrote based on a misunderstanding of the problem (but read on!):
I think the meaning must be that $k$ is the sum of the coefficients of $P_n$ or in other words $k=P_n(1)$.
If that is the case, you don't need to care about the values of the polynomials for $x$s other than $1$, and the recurrence collapses into
- $k_0=l_0=1$
- $k_n = k_{n-1} + l_{n-1}$
- $l_n = k_{n-1} - l_{n-1}$
Since this is a linear recurrence, we can express it as a matrix power: $ \begin{pmatrix}k_n \\ l_n\end{pmatrix} = > \begin{pmatrix}1&1\\1&-1\end{pmatrix}^n\begin{pmatrix}1\\1\end{pmatrix}$ The characteristic polynomial of $\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ is $(1-t)(-1-t)-1=t^2-2$, so it has eigenvectors with eigenvalues $\pm\sqrt2$, and $\begin{pmatrix}1\\1\end{pmatrix}$ is some linear combination of them. Therefore $k_n$ will be $a(\sqrt2)^n+b(-\sqrt2)^n)$ for some nonzero $a$ and $b$ that we don't need to calculate explicitly -- the important point is that $\frac{a(\sqrt2)^n}{2^n}$ and $\frac{b(-\sqrt2)^n}{2^n}$ both go towards $0$ no matter what $a$ and $b$ are; therefore $\frac{k_n}{2^n}\to 0$ too.
More elementarily, we can also just compute $(k_n,l_n)$ for the first few $n$s and look for patterns: $ \begin{array}{c|cc} n & k_n & l_n \\\hline 0 & 1 & 1 \\ 1 & 2 & 0 \\ 2 & 2 & 2 \\ 3 & 4 & 0 \\ 4 & 4 & 4 \end{array}$ This clearly suggests that $l_{2m}=k_{2m}=k_{2m-1}=2^m$ and $l_{2m-1}=0$, and we can then prove that this is the case by an easy induction.
Now it turned out that the question was not actually about the sum of all coefficients of $P_n$, but about the number of coefficients of $P_n$ that happen to be $1$. But what we have done so far can actually be salvaged. We now start by proving:
The degree of $P_n$ and $Q_n$ is always $2^n-1$. (Proof: simultaneous induction on $n$).
Every coefficient of $P_n$ and $Q_n$ is $\pm 1$. (Proof: simultaneous induction on $n$, using the previous result in the induction step).
Now the number we're really after is the number of $1$ coefficients in $P_n$. Let's write that as $K_n$ rather than $k_n$ to reduce confusion with the "wrong" $k_n$ in the above calculation. Because all coefficients are either $1$ or $-1$, we have $ P_n(1) = -2^{n} + 2K_n $ where the $-2^n$ term assumes that all coefficients are $-1$ and $2K_n$ corrects for those that are actually $+1$. Solving for $K_n$ gives $ K_n = \frac{P(1)+2^n}{2} $ So the limit we're after is $ \lim_{n\to\infty} \frac{K_n}{2^n} = \lim_{n\to\infty} (\frac{O(\sqrt 2^n)}{2^n} + \frac12) = \frac 12 $ where we use $P(1)=O(\sqrt 2^n)$ from the above solution-to-the-wrong-question.
So the sought-for limit is $\frac 12$.