Let $M>0$ be fixed. Consider the set $S := \{y\in \mathbb{R}\mid |P(y)|\leq M \}$. It's bounded, since $P$ can't be a constant polynomial, except for the constant $0$. Let $M_1>0$ be such that $|y|<M_1\,,\,\forall y\in S$. It boils down to prove that for sufficiently large $n$, for any monic polynomial $Q$ of degree $n$, the number of the integers $k$ for which $|Q(k)|<M_1$ is at most $n$. In order to get contradiction suppose $n$ is sufficiently large, say $n\geq d$ where the value of $d$ will be chosen later. Suppose also there is a monic polynomial $Q$ of degree $n$ and $n+1$ integers $k_1<k_2<\dots,<k_{n+1}$ for which $|Q(k_i)|<M_1\,,\,i=1,2,\dots,n+1$. Let us try to construct a monic polynomial $Q_1$ of degree $n$ for which $Q(k_i)=(-1)^i a\,,\,i=1,2,\dots,n+1$, for some $a\in\mathbb{R}$. Using Lagrange interpolation, we can construct for any $a$, a polynomial $L(x)=a_0 x^n +a_1x^{n-1}+\dots+a_n\,,\,L(k_i)=(-1)^i a$. It's senior coefficient equals: $$a_0=a\sum_{j=1}^{n+1} (-1)^j\prod_{i\neq j}\frac{1}{k_j-k_i} $$ Hence, for $a:=\left(\sum_{j=1}^{n+1} (-1)^j\prod_{i\neq j}\frac{1}{k_j-k_i} \right)^{-1}$, $L(x)$ becomes monic. We denote it by $Q_1(x)$. Let's estimate $|a|$. $$|a| \geq \left(\sum_{j=1}^{n+1}\prod_{i\neq j}\frac{1}{|k_j-k_i|}\right)^{-1}\geq \frac{\left\lfloor\frac{n}{2} \right\rfloor !}{n}$$Since, the RHS grows as big as we want, we can make the postponed choice of $d$, such that $n>d\implies |a|>M_1$. Let us recap the situation now. We have a monic polynomial $Q$ of degree $n$ with $|Q(k_i)|<M_1\,,\,i=1,2,\dots,n+1$. We also have a monic polynomial $Q_1$ with $Q_1(k_i)=(-1)^i a\,,\,i=1,2,\dots,n+1$, where $|a|>M_1$. Consider the polynomial $R(x):=Q_1(x)-Q(x)$. It's of degree $n-1$, since $Q,Q_1$ are monic. $R$ alternatively changes its sign at the points $k_1,k_2,\dots,k_{n+1}$ due to the fact $|Q_1|$ majorates $|Q$| at these points and $Q_1$ alternatively changes its sign. It means there exist $\xi_i\in (k_i,k_{i+1})\,,\,R(\xi_i)=0\,,\,i=1,2,\dots,n$. Since $\deg R\leq n-1$, it implies $R\equiv 0$, a contradiction. Thus, for any $n>d$ and any monic $Q$ of degree $n$, $|P(Q(k))|\leq M$ holds for at most $n$ different integer values of $k$. Comment: $P(0)=0$ is used only to ensure $P$ is not constant, except for the constant $0$. The fact that $k_i$ are integers, was used only to ensure there is enough space between them. So, it can be made similarly for any such system of points. That idea of constructing other monic polynomial with alternating deviation signs is commonly used in uniform approximation with polynomials and originates from Chebyshev (his alternation approximation theorem).

What if $P(x) \equiv 0$ ?

Rickyminer wrote: What if $P(x) \equiv 0$ ? The original problem had non-zero conditon which I added now.

Note that the solutions of $|P(x)| \leq M$ is a interval which is a subset of a interval of the form $(-a,a)$ , for some $a \in \mathbb R$ Assume $\operatorname {deg} Q = n \geq d$ .Pick any $n+1$ integers $x_0,x_1, \dots , x_n$ . By Lagrange Interpolation we have $:=$ $$Q(x) = \sum_{i=0}^n Q(x_i) \prod_{j \neq i} \frac {x-x_j}{x_i-x_j}$$ Since $Q$ is monic we have that $:=$ $$1 = \sum_{i=0}^n Q(x_i) \prod_{j \neq i} \frac 1{x_i-x_j}$$ We will bound the RHS as $:=$ $$1=\sum_{i=0}^n Q(x_i) \prod_{j \neq i} \frac 1{x_i-x_j} \leq \operatorname {max}_i Q(x_i) \sum_{i=0}^n \prod_{j \neq i} \frac 1{x_i-x_j} \leq \operatorname {max} Q(x_i) \sum_{i=0}^{n} \frac 1 {i! (n-i)!} = \frac {2^n}{n!} \cdot \operatorname {max} Q(x_i) $$$$\implies \operatorname {max} Q(x_i) \geq \frac {n!}{2^n} \geq \frac {d!}{2^d} $$ Call the above equation $\spadesuit$ Now we choose $d$ such that $|\frac {d!}{2^d}| < |a| .$ Note that the condition $\spadesuit$ implies that amongst any $n+1$ integers $\{x_i\}_{i=0}^n$ atleast one of them must satisfy the inequality in $\spadesuit$ . However all solutions to $|P(Q(x))| \leq M$ must satisfy $|Q(x)| \leq \frac {d!}{2^d}$ , and there are atmost $n$ such integers , as desired $\blacksquare$

Proposed by Navid Safaei.