Assume $p,q\in P^{(n)}$ are two polynomials with the same coefficients except for the first two where $p(x)=1+2x+...$ and $q(x)=2+x+...$. since $d|p(k)$ and $d|q(k)$, it follows that $d|p(k)-q(k)=2k+1-2-k=k-1$, and so $k\equiv 1\pmod{d}$. Therefore for every $p\in P^{(n)}$ $p(k)\equiv p(1)=1+2+\cdots+2^n=2^{n+1}-1\pmod{d}$ which we need to be $0\pmod{d}$. What this means is that there needs to be at least one such $n$, which happens exactly when $d$ is odd. Therefore, all possible pairs are $(b(2a+1)+1,2a+1)$ for any nonnegative $a$ and $b$.

Suppose such a $\mathcal{P}^{(n)}$ exists for some $(k, d)\in \mathbb{N}^2$. First of all, clearly $d$ is odd. Take two polynomials having their their first $n-1$ coefficients equal and the last two coefficients being $2^1, 2^0$ in reverse order, this implies that $d$ has to divide $k-1$. Now we prove its sufficiency. Pick two arbitrary polynomials $P_1, P_2\in \mathcal{P}^{(n)}$ such that $d\mid P_{1}(k)$, then obviously $$P_{1}(k)\equiv P_{1}(1)\equiv P_{2}(1)\equiv P_{2}(k)\pmod{d}$$So, the answer is $\{k, d\}=\{l(2k+1)+1, 2k+1\}$.