$\renewcommand\bar\overline$Indeed, it is not obvious why "$u'_{n_k} \to \overline{u}'$ in the sense of $L^r[a,b]$".
Look at this example: $[a,b]=[0,2\pi]$, $u_n(x)=\dfrac{\sin nx}n$, $\bar u=0$. Then $u_n\to\bar u$ uniformly, but $u_{n_k}'\not\to\bar u'$ in $L^r$ for any increasing sequence $(n_k)$ of natural numbers, because $u_n'(x)=\cos nx$ and hence $\|u_n'\|_r^r=c_r:=\int_0^{2\pi}|\cos u|^r\,du>0$ for all $n$.
Note also that your argument does not use the condition that $g$ is convex.
(Also, your post seems to have hardly anything to do with the Tonelli theorem.)
Here is how to fix this. Using, as you did, the Arzelà–Ascoli theorem and then passing to a subsequence, without loss of generality (wlog) we may assume that $u_n\to \bar u$ uniformly. Also, you showed that the sequence $(u_n')$ is bounded in (the reflexive Banach space) $L^r$.
So, by the Eberlein–Shmulyan theorem (Kôsaku Yosida, Functional Analysis, Springer 1980, Chapter V, Appendix, section 4; alternatively, see e.g. this version), passing again to a subsequence, wlog we may assume that $u_n'\to v$ for some $v\in L^r$ in the weak topology of $L^r$.
Further, by Mazur's lemma, for each natural $n$ there exist a natural $N_n\ge n$ and nonnegative real numbers $a_{n,k}$ for $k\in\{n,\dots,N_n\}$ such that $\sum_{k=n}^{N_n}a_{n,k}=1$ and
\begin{equation*}
v_n:=\sum_{k=n}^{N_n}a_{n,k} u_k'\to v \tag{0}
\end{equation*}
in $L^r$.
For $x\in[a,b]$, let now
\begin{equation*}
w_n(x):=u_n(a)+\int_0^x v_n(t)\,dt
=u_n(a)-\sum_{k=n}^{N_n}a_{n,k}u_k(a)+\sum_{k=n}^{N_n}a_{n,k}u_k(x). \tag{1}
\end{equation*}
Since $u_n\to \bar u$ uniformly and the $u_n$'s are uniformly bounded, we see that $w_n\to \bar u$ uniformly and the $w_n$'s are uniformly bounded. Therefore and because $f$ is continuous, we have
\begin{equation*}
J_1[w_n] := \int_a^b f(x,w_n(x))\, dx\to J_1[\bar u]=\lim_n J_1[u_n].
\end{equation*}
Also, by the convexity of $g(x,\xi)$ in $\xi$,
\begin{equation*}
J_2[w_n] := \int_a^b g(x,w_n'(x))\, dx
\le\sum_{k=n}^{N_n}a_{n,k}J_2[u_k].
\end{equation*}
Also, $J[w_n]=J_1[w_n]+J_2[w_n]$. So,
\begin{equation*}
\begin{aligned}
\limsup_n J[w_n]&\le \lim_n J_1[w_n]+\limsup_n J_2[w_n] \\
&\le \lim_n J_1[u_n]+\sum_{k=n}^{N_n}a_{n,k}\limsup_n J_2[u_n] \\
&= \lim_n J_1[u_n]+\limsup_n J_2[u_n] \\
&= \limsup_n (J_1[u_n]+J_2[u_n]) \\
&= \limsup_n J[u_n]= \lim_n J[u_n]=\inf_{u\in X} J[u].
\end{aligned}
\end{equation*}
So, passing to a subsequence, wlog we may assume that
\begin{equation*}
J[w_n]\to\inf_{u\in X} J[u].
\end{equation*}
Recall that $w_n\to \bar u$ uniformly. So, in view of (1) and (0),
\begin{equation*}
\bar u(x)=\bar u(a)+\int_0^x v(t)\,dt
\end{equation*}
for $x\in[a,b]$, so that $\bar u\in AC$ and $\bar u'=v$ almost everywhere (a.e.).
It also follows that $w_n'=v_n\to v=\bar u'$ in $L^r$ and hence in measure. So, by the continuity of $f$ and $g$ and the Fatou lemma,
\begin{equation}
J[\bar u]=J[\lim_n w_n]\le\liminf_n J[w_n]=\lim_n J[w_n]=\inf_{u\in X} J[u].
\end{equation}
It is also easy to see that $\bar u\in X$. Thus, $\bar u$ is a minimizer of $J[u]$ over $u\in X$.
I hope I did not misunderstand the question, but it seems $\varphi(x) > - \infty$ holds as follows if $(x, y) \in \Gamma$:
For any $(x_i, y_i) \in \Gamma$, $i=1, \dots, n$, we see that
\begin{align}
&c(x, y_{n}) - c(x_n, y_n) + \sum_{i=0}^{n-1} c(x_{i+1}, y_i) - c(x_i, y_i) \\
&= c(x, y_{n}) - c(x_n, y_n) + \sum_{i=0}^{n-1} c(x_{i+1}, y_i) - c(x_i, y_i) \\&+ c(x_0, y) - c(x, y) -c(x_0, y) + c(x, y) \\
&= - c(x, y) + c(x, y_n) - c(x_n, y_n) + c(x_n, y_{n-1}) - ... + c(x_1, y_0) - c(x_0, y_0) + c(x_0, y) \\
&+c(x, y) - c(x_0, y) \\
&\geq c(x, y) - c(x_0, y) > -\infty,
\end{align}
where the last inequality holds since $(x, y) \in \Gamma$ and by $c$-cyclical monotonicity of $\Gamma$.
Thus, $\varphi(x)$ is bounded from below by $c(x, y) - c(x_0, y)$.
Best Answer
Are you sure there aren’t additional conditions on $\varphi$? Because otherwise taking $X = \mathbb R$ and $Y$ to be a one point space, the following gives a counterexample:
$c(x, y) = 0$ if $x = 0$; $c(x, y) = 1$ otherwise, and
$\varphi(x) = 0$ if $x = 0$, $\varphi(x)= 2$ otherwise.
Indeed, $\varphi^c = -1$, while $\psi_\ell \leq -2$ for all $\ell$.
My guess is that $\varphi$ should be restricted to be continuous.