Note that $(k+1)-0 = F(k+1)-F(0)$. Since $|F(k+1)-F(0)| \le k$, we must have $F(k+1) = F(0) = d$ for some constant $d$. Let $F(x) = d + x(x-k-1)G(x)$ for some polynomial $G$ with integer coefficients.

For $2 \le n \le k-1$, we have $F(n) = d+n(n-k-1)G(n)$, and so $n(k+1-n) \mid F(n)-d$.
Again, $|F(n)-d| \le k$. Since $n(k+1-n) \ge 2(k+1-2) > k$, we must have $F(n) = d$.
Thus, we can write $F(x) = d+x(x-2)(x-k+1)(x-k-1)H(x)$ for some polynomial $H$ with integer coefficients. (Note that we have used the fact $k \ge 4$ to show that the roots $0, 2, k-1, k+1$ of $F(x)-d$ are distinct.)

Lastly, for $n = 1, k$, we have $n(n-2)(n-k+1)(k+1-n) \mid F(n) - d$. Again, $|F(n)-d| \le k$. Also, $n(n-2)(n-k+1)(k+1-n) = k(k-2) \ge 2k$ in both cases. Therefore, we must have $F(n) = d$.

Thus, we have shown that $F(n) = d$ for $n = 0, 1, \dots, k+1$.