Up to this point I have proved that the approximation $||u_k||_{L^{p^*}}< C||\nabla u_k||_{L^{p}}$ for smooth compactly supported functions $u_k$. By density of $C^\infty_c$ in $W^{1,p}$, I would like to pass to the limit of $u_k$ in $W^{1,p}$. My attempt at this would like to go $||u-u_k||_{L^{p^*}}<C||\nabla u-\nabla u_k||_{L^{p}}\rightarrow 0$. But we do not know that $u$ is a priori in $L^{p^*}$. So how do we proceed.
More abstractly perhaps, suppose that we have Banach spaces $X,Y$, a continuous embedding of a dense subset of $X$ into $Y$. Can we conclude that the continouous embedding can be extended to the whole of $X$?
The usual direct argument is as follows. Let $u \in W^{1,p}$ and take $u_k \in C_c^\infty$ such that $u_k \to u$ in $W^{1,p}$. You are right that we cannot immediately conclude that $u \in L^{p^*}$.
However, we do know that $u_k$ must be a Cauchy sequence in $W^{1,p}$ since it converges. Since $u_m - u_n \in C_c^\infty$, from what you've already proven we have $$\|u_m - u_n\|_{L^{p^*}} \leq C \| \nabla u_m - \nabla u_n\|_{L^p} \leq C \|u_m - u_n\|_{W^{1,p}}$$ so $u_k$ is also Cauchy in $L^{p^*}$ and hence $u_k \to \tilde{u}$ in $L^{p^*}$. It remains to check that $\tilde{u} = u$ a.e. You can do this by passing to a subsequence such that $u_{n_k} \to u$ a.e. and $u_{n_k} \to \tilde{u}$ a.e.
As you noted, it is possible to abstract parts of this a little.
The idea of the first part of the above argument will establish that if $Y$ is a Banach space, $X_0$ is a dense subspace of $X$ and $T:X_0 \to Y$ is a bounded linear operator then $T$ has a unique bounded linear extension to a map $X \to Y$ and this extension is of the same norm as $T$.
Applied in this case, this general result would say that $\operatorname{Id}: (C_c^\infty, \|\cdot\|_{W^{1,p}}) \to L^{p^*}$ has a unique linear extension of the same norm to a map $T: W^{1,p} \to L^{p^*}$. You then want to check that $T$ is just the map $u \mapsto u$. This is what the second part of the above argument does in this case.