I address the real (and sometimes complex) case. We always assume $P$ to be monic. I deal with the original condition, but that in Q3 can be dealt with analogously.
1. After a substitution $Q(x)=P(x-\frac12)$, we come to a more symmetric set up
$$
Q(x)\mid \left(x+\frac12\right)^kQ(x+1)+\left(x-\frac12\right)^kQ(x-1)=:R(x).
$$
Let $\xi_1,\dots,\xi_n$ be the complex roots of $Q$ counted with multiplicity.
Assume that some $\xi_i$ has a positive real part. Let $\xi$ be a root with the maximal real part. Then
$$
\left|\left(\xi+\frac12\right)^kQ(\xi+1)\right|
=\left|\xi+\frac12\right|^k\prod_t|\xi-\xi_t+1|
>\left|\xi-\frac12\right|^k\prod_t|\xi-\xi_t-1|
=\left|\left(\xi-\frac12\right)^kQ(\xi-1)\right|,,
$$
so $R(\xi)$ cannot vanish. This is impossible. The case when some root has negative real part is ruled out similarly.
Hence, $\xi_t=ix_t$ for some real numbers $x_t$. This already shows
$$
Q(-x)=\prod_t(-x-ix_t)=(-1)^n\prod_i(x+ix_t)=(-1)^n\overline Q(x),
$$
which means $P(x+1)=(-1)^n\overline P(x)$, as suggested by @PeterMueller in the comments. In the real case, this confirms Q2.
2. Surely, the restrictions on the $x_t$ is stronger. Set
$$
T(x)=\left(ix+\frac12\right)^k\prod_{t\neq s}(i(x-x_t)+1);
$$
then for every $x\in\mathbb R$ we have
$$
R(ix)=T(x)+(-1)^{k+n}\overline{T(x)}.
$$
Hence we should have $T(x_s)=(-1)^{k+n+1}\overline{T(x)}$, so the real/imaginary part (depending on the parity of $k+n$) of $T(x_s)$ should vanish for all $s$. In other words, the function
$$
f(x)=k\arctan (2x)+\sum_{t}\arctan(x-x_t) \qquad(*)
$$
should attain values in $[\frac\pi2+]\pi\mathbb Z$ at all $x=x_s$.
Notice that these conditions are also sufficient if all the $x_t$ are distinct.
3. Now we aim at showing that, for many pairs $(k,n)$, there exists at least one desired polynomial $Q$. This partially answers Q1.
Case OE. Assume that $k$ is odd and $n<2k$ is even; then all the $T(x_s)$ should be real. In this case, we should have $f(x_s)\in\pi\mathbb Z$.
Choose a large number $N$. Consider the set
$$
X=\left\{(x_i,\dots,x_n)\in\mathbb R^n\colon -N\leq x_1,\leq x_2\leq\dots\leq x_n\leq N, \; x_t=-x_{n+1-t}\right\}.
$$
Now define a mapping $\phi\colon X\to\mathbb R^n$, $(x_1,\dots,x_n)\mapsto (y_1,\dots,y_n)$, where $y_m<0$ ($m\leq n/2)$ is the unique solution of
$$
f(y_m)=\left(m-\frac n2-1\right)\pi,
$$
and $y_m=-y_{n+1-m}$. (Recall that the definition of $f$ in $(*)$ depends on the $x_i$.)
Now, if $N$ is large, then $f(-N)\leq -\frac\pi2k-\frac\pi2\cdot \frac n2+\varepsilon<-\frac \pi2 n$, so that all the $y_i$ lie on $[-N,N]$. Moreover, $f$ is strictly increasing, so that $-N\leq y_1<\dots<y_n\leq N$. Hence $\phi$ is a (continuous) mapping from $X$ to itself, and it has a fixed point by Brouwer's therem.
Due to the definition of $\phi$, all the coordinates of that fixed point are distinct, so it provides a desired polynomial $Q$. According to the definition of $X$, the coefficients of $Q$ are real.
Surely, if $2k-n$ is larger than $2$, this construction allows variations.
Case OO. Assume that both $k$ and $n$ are odd. This case is impossible, for a real polynomial $Q$, since $Q$ should have a real root $x_s$, and at this root $T(x_s)$ is real and nonzero. However, complex polynomials can be found in the same way.
Cases EO and EE are similar to the case OE. In the case EO, we need to ensure that one of the roots of $Q$ is zero.
Remark. The cases where $n$ is much larger than $k$ look harder, as we need to ensure that $\phi$ maps $X$ to itself. Perhaps, one can redefine $X$ so that the construction would work in this case as well?
