We call the number $m + k$ from the problem condition convenient if it has at least $n$ distinct prime divisors, otherwise we call the number $m + k$ inconvenient. It is easy to see that we may consider inconvenient numbers only. Take one of them, $m + k = q_1^{a_1} q_2^{a_2} \dots q_l^{a_l}$, where all $q_i$ are primes, $l \le n - 1$. Since
$$q_1^{a_1} q_2^{a_2} \dots q_l^{a_l} = m + k > n^{n-1} \ge n^l,$$
there exists an $i$ with $q_i^{a_i} > n$, so we can choose $p_k = q_i$. In a similar way we can choose prime divisors for other inconvenient numbers. It remains to note that for different inconvenient numbers the chosen prime divisors are different.