Funny problem! We claim that all pairs $(m, n)$ are $(2k+1, n)$ for all $k, n \in \mathbb{N}$ and $(2a, 2b)$ for all $a, b \in \mathbb{N}.$ Our first step will be to show that no other pairs work. When $m = 1$, we can just take $P(x) = x+1$ to see that $(1, n)$ fails for all $n \in \mathbb{N}.$ Now, all that remains to complete the first step is to check that $(m, n)$ fails for $m$ even, $n$ odd. We claim that taking $P(x) = x^m + m-1$ implies this. Observe that this $P(x)$ satisfies the property that $P(x) - x > 0$ for all $x \in \mathbb{R}.$ To see this, note that it's clear for $x \le 0$ and when $x \ge 0$ we've that $x^m + m-1 = x^m + 1 + 1 + \cdots + 1 \ge mx > x.$ We claim that this then guarantees that no such $Q$ of odd degree exists. Indeed, let's use the deep fact that all odd-degree polynomials have at least one root. Suppose, for contradiction, that some $Q$ of odd degree $n$ existed such that $Q(x) | Q(P(x)).$ With this, taking the root $r$ of $Q$ which is the biggest and plugging it into this equation implies that $Q(P(r)) = 0$. However, this implies that $P(r)$ is also a root of $Q$, which contradicts the minimality of $r$ since $P(r) > r.$ Hence, we've now completed the first step. In the second step, we need to show that all claimed pairs indeed work. First of all, observe that if $Q(x) | Q(P(x))$, then the polynomial $Q_1(x) = Q(x)^k$ also satisfies $Q_1(x) | Q_1(P(x)),$ as this simply follows by raising the first divisibility relation to the $k$th power. With this in mind, we need only to show that $(2a+1, 1)$ and $(2a, 2)$ work for all $a \in \mathbb{N}.$ Let $P$ be a polynomial of degree $2a+1$, for some $a \in \mathbb{N}.$ Notice that $P(x) - x$ has degree $2a+1$ as well, and hence has some real root $r$. Then, we have that $x-r | P(x) - x \Rightarrow x-r | P(x) - r$, which means that $Q(x) = x-r$ satisfies $Q(x) | Q(P(x)),$ i.e. $(m, n) = (2a+1, 1)$ works. Now let $P$ be a polynomial of degree $2a$, for some $a \in \mathbb{N}.$ If $P(x) - x$ has a real root $r$, then we can take $Q(x) = (x-r)^2$ to get a working pair. Otherwise, let's take a complex root $r$ of $P(x) - x.$ Since $P(x) - x$ has real coefficients, $r$'s complex conjugate $\overline{r}$ is also a root of it. Then, we claim that $Q(x) = (x-r)(x-\overline{r})$ works. Indeed, observe that $Q(P(x)) = (P(x) - r)(P(x) - \overline{r})$ has $r$ as a root since $P(r) = r$ and has $\overline{r}$ as a root since $P(\overline{r}) = \overline{r}.$ This implies that $Q(x) = (x-r)(x- \overline{r})$ works, and so $(2a, a)$ works. Combining the above work, we are now done. $\square$