Let's write the function as $f(x,k)$.
For $k = 0$, the polynomial $f(x,0) = - 2 x^{n-1} - 1$ has no positive roots. For $k = 1$, $f(x,1) = x^n - 3 x^{n-1} - 2$ has a real root greater than $3$. For $k = 2$, $f(x,2) = x^{n-2} (x^2 - 2 x - 1) - 4 > 0$ if $x \ge 3$ and $n \ge 3$. For $k = n$, $f(x,n) = x^{n-1}(x - 2) - 1 - 2^n > 0$ if $x \ge 3$ and $n \ge 3$. Now $f(x,k)$ is a concave function of $\log_2(k)$ for fixed $x > 1$, so $f(x,k) > 0$ if $x \ge 3$, $n \ge 3$ and $2 \le k \le n$. Thus if $n \ge 3$, the greatest real root of $f(x,k)$ for integers $0 \le k \le n$ occurs at $k=1$.
Since the companion matrix of the polynomial $f(x,k)$ has nonnegative entries, the Perron-Frobenius theorem shows that the greatest real root is also the greatest in absolute value.
If we plot the roots, the picture is rather striking. Here is an animation showing the case $n=100$. For each $k\ge 1$ it appears that we have one positive root (near $x=3$ for $k=1$, decreasing rapidly to near $2$, and finally increasing slightly for $90 < k \le 100$), the other roots almost in a circle centred at $0$, of radius less than the real root, that expands as $k$ increases.
