Belarusian Mathematical Olympiad

Answer: all $(m, n)$ with odd $m$ and arbitrary $n$; or $(m, n)$ with even $m$ and even $n$.
(Solution of A. Zhuk.)

1. Let $m$ be odd. Show that any positive $n$ is appropriate.
Indeed, if $P(x) \equiv x$, then $Q(P(x)) \not\equiv Q(x)$ for any $Q \in \mathbb{R}[x]$.
If $P(x) \not\equiv x$, then $P(x) - x$ is a polynomial of odd degree, hence it has a real root, say, $a$. Then for any $n \in \mathbb{N}$ consider $Q(x) = (x-a)^n$. We have $Q(P(x)) = (P(x)-a)^n$. Note that $P(x)-a = (P(x)-x+(x-a)) \not\equiv (x-a)$. Hence $(P(x)-a)^n \not\equiv (x-a)^n = Q(x)$, as we need.

2. Now, let $m$ be even. First, show that $n$ cannot be odd. Set, for example, $P(x) = x^m + x + 1$. Then $P(x) - x > 0$ for any $x \in \mathbb{R}$. If $n$ is odd, then $Q(x)$ has real roots. Let $c$ be the largest real root of $Q$. That is
$$Q(x) = b(x-c) \prod_{i=1}^{k} (x-a_i) \cdot \prod_{j=1}^{l} q_j(x),$$
where all $q_j(x)$ are monic quadratic polynomials with negative discriminants, $c \ge a_i$ for all $i = 1, 2, ..., k$, $b \ne 0$.
Then
$$Q(P(c)) = b(P(c)-c) \prod_{i=1}^{k} (P(c)-a_i) \cdot \prod_{j=1}^{l} q_j(P(c)).$$
Note that $P(c)-c > 0$, $P(c)-a_i > c-a_i \ge 0$, $(\forall i = 1, ..., k)$, $q_j(P(c)) > 0$ $(\forall j = 1, ..., l)$, that is $Q(P(c)) \ne 0$. Hence, $c$ is not a root of $Q(P(x))$, so $Q(P(x)) \not\equiv Q(x)$.

Let now both $m$ and $n$ be even, $n = 2k$.
If $P(x) - x$ has a real root $a$, then, as above, we set $Q(x) = (x-a)^n$, and we are done.
Let $P(x) - x$ has no real roots. Let $z$ and $\bar{z}$ be any complex-conjugate roots of $P(x)$, that is $P(x) - x$ is divisible by $p(x) = (x-z)(x-\bar{z}) \in \mathbb{R}[x]$. Set $Q(x) = (p(x))^k$. Then $Q(P(x)) = (p(P(x)))^k$. It suffices to prove that $p(P(x)) : p(x)$. Note that $p(P(x)) = p(P(x)) - p(x) + p(x)$ and
$$(p(P(x)) - p(x)) : (P(x) - x) : p(x).$$
Therefore,
$$Q(P(x)) = (p(P(x)))^k : (p(x))^k = Q(x).$$