One alternative argument would be as follows:
If there exists a $\rho\ge0$ such that $\Phi\otimes \mathrm{Id}_k(\rho)\not\ge0$, then there will also exist a pure $\vert\chi\rangle$ such that $\Phi\otimes \mathrm{Id}_k(\vert\chi\rangle\langle\chi\vert)\not\ge0$. (This follows immediately from convexity, e.g. by taking an ensemble decomposition of said $\rho$ -- it will contain one such $\vert\chi\rangle$.)
Take the Schmidt decomposition of $\vert\chi\rangle$, and denote its Schmidt rank by $\ell$. Clearly, $\ell\le n$. Then, when considering $\Phi\otimes \mathrm{Id}_k(\vert\chi\rangle\langle\chi\vert)$, the extending space (the one with the $\mathrm{Id}$) can be compressed to a space with dimension $\ell$ (spanned by the Schmidt vectors). Call the compressed state $\vert\chi'\rangle$.
Clearly, in the compressed space $\Phi\otimes Id_\ell(\vert\chi'\rangle\langle\chi'\vert)\not\ge0$.