The Sobolev inequalities allow one to trade regularity (in the sense of derivatives) for integrability. Namely, you can trade a derivative at a lower integrability exponent $p$ for a higher integrability exponent $q=p^*=\frac{np}{n-p}>p$ (exponents $q$ in between can be obtained from Hölder's inequality if $U$ is assumed to be bounded as you do). You can iterate this inequality as many derivatives as you want, of course. Moreover, this inequality is sharp (see the last paragraph below). By looking e.g. at the proof by Gagliardo and Nirenberg reproduced e.g. in Theorem 5.6.1, pp. 277-279 of the book by Lawrence C. Evans, Partial Differential Equations, 2nd. ed., AMS, 2010, one sees that this trade comes essentially from the fundamental theorem of Calculus.
(Edit: Such an inequality is aided by another (also called Sobolev's) inequality, which is valid for $p>n$: suppose that $U$ and $u$ are as you stated for such a $p$ - then $u\in L^\infty(U)$ and satisfies the estimate $$\|u\|_{L^\infty(U)}\leq C\|u\|_{W^{1,p}(U)}\ .$$ In fact, $u$ is then even continuous since smooth elements of $W^{1,p}(U)$ are dense therein. The proof of this inequality is simple - after multiplying $u$ by a radial cutoff function $\psi$ supported in the interior $\mathrm{int}\ U$ of $U$, centered around a given point $x$ of $\mathrm{int}\ U$ and with integral 1, one passes to spherical coordinates centered at $x$ and applies the fundamental theorem of Calculus to the radial coordinate. The argument is closed by applying Hölder's inequality (for details, see e.g. the Appendix from the book by Christopher D. Sogge, Lectures on Non-Linear Wave Equations, 2nd. ed., International Press, 2008). Once more, one sees that the allowed trade between regularity and integrability comes from the fundamental theorem of Calculus. Higher derivatives are obtained by applying the Gagliardo-Nirenberg-Sobolev inequality you stated to the rhs of the above as many times as needed. Conversely, the Gagliardo-Nirenberg-Sobolev inequality for $p>1$ can be obtained from a similar argument - plus a technical lemma due to Hardy, Littlewood and Sobolev regarding the boundedness of convolution with the function $g(x)=\|x\|^{1-n}$ -, which is actually due to Sobolev himself)
What is this important for? Recall that, unlike for $p=\infty$, derivatives in Sobolev spaces for $p<\infty$ are distributional or weak derivatives: namely, if $f\in W^{1,p}$, one defines the weak partial derivative $\partial_j f$ in the $j$-th variable by formally integrating by parts against a smooth function $\phi$ compactly supported in the interior $U$ (recall that the boundary of $U$ has zero $n$-dimensional Lebesgue measure and weak derivatives need only to be defined almost everywhere): $$\int_U (\partial_j f(x))\phi(x)\mathrm{d}^nx\doteq-\int_U f(x)\partial_j\phi(x)\mathrm{d}^nx\ .$$ The definition of $W^{1,p}(U)$ states that $\partial_j f\in L^p(U)$ for all $j$.
Using Sobolev's inequality, if we set $q=\infty$ (see Edit above!) we turn the remaining, "untraded" weak derivatives of $f$ into classical derivatives. This is of extreme importance in the study of linear partial differential equations (for which Sobolev spaces were originally devised, by the way), for it is easy to obtain weak solutions in Sobolev spaces (that is, the derivatives in the partial differential operator act as weak derivatives) by using certain a priori inequalities depending on the kind of operator you are studying (elliptic, hyperbolic, etc.). If weak solutions have enough regularity, one can use the Sobolev inequality to show they are solutions in the usual sense - that is, the derivatives in the partial differential operator actually act on such solutions as classical derivatives. Check my answer to this other math.SE question of yours for an example of this.
In the case where $U$ is no longer bounded, since integrability entails a certain decay towards infinity, the bounds on the possible trade between integrability and regularity allowed by Sobolev's inequality on such an $U$ may be seen physically as an uncertainty principle in the sense of quantum mechanics - in fact, the family of uncertainty principles derived from Sobolev's inequality is far more precise than Heisenberg's original statement and plays a key role in the proof of stability of quantum matter.
Ah yes, I almost forgot to mention its important geometrical interpretation: if you take $n>1$, $f$ equal to the characteristic function of $U$, $p=1$ and $q=p^*=\frac{n}{n-1}$, the Sobolev inequality becomes the isoperimetric inequality in $\mathbb{R}^n$, which states that the isoperimetric ratio $$\frac{V^{\frac{n-1}{n}}}{A}\ ,$$ where $V$ is the $n$-dimensional volume of a bounded region $U$ with finite perimeter and $A$ is the $(n-1)$-dimensional area of its boundary (here "finite perimeter" means that $A$ is well defined and finite), is less than or equal to the same ratio for a $n$-dimensional ball (= the so-called isoperimetric constant of $\mathbb{R}^n$), with equality only in this case - that is, the inequality is sharp, as claimed in the first paragraph. The isoperimetric constant of $\mathbb{R}^n$, by the way, is the optimal value of the constant $C$ for $p=1$. The argument can be extended to other Riemannian manifolds which enjoy some form of the isoperimetric inequality (possibly with a different isoperimetric constant). For a thorough discussion on these matters, check out the excellent book Some Nonlinear Problems in Riemannian Geometry by Thierry Aubin (Springer, 1998).
Best Answer
Since $u_k\to u$ in $W^{1,p}\subset L^1_{loc}$ ($L^1$ when restricted to compact subsets of $\mathbb R^n$) and $u_k\to \tilde u$ in $L^{p^*} \subset L^1_{loc}$, it follows that $u=\tilde u$. So $u=\tilde u\in L^{p^*}\cap W^{1,p}$.
Furthermore, if $(X,\|\cdot\|_X)$ is any normed space, then by rearranging the triangle inequality $\|u+v\|_X \le \|u\|_X + \|v\|_X$ we obtain $$ |\|u\|_X-\|v\|_X| \le \|u-v\|_X$$ Applying this to our Banach spaces, $$\|u_k\|_{L^{p^*}} \to \|u\|_{L^{p^*}} ,\quad \|\nabla u_k \|_{L^p} \to \|\nabla u\|_{L^p}$$
Thus we may pass to the limit in the norm inequality.