I would highly appreciate any clues as I can't think of a starting point other than to intuitively claim that it "makes sense" and finding examples for which it works... And could this proof be extended to curves that can't be represented as functions?
Here is an example (which I checked and worked):
Everything works in $\Bbb R^n$:
Let the two curves be
$p:I_1 \to \Bbb R^n, \tag 1$
$q:I_2 \to \Bbb R^n, \tag 2$
where $I_1, I_2 \subset \Bbb R^n$ are (open) intervals. The distance between points $p(t)$ and $q(s)$ is
$\sigma(p, q) = \sigma(t, s) = ((p(t) - q(s)) \cdot (p(t) - q(s)))^{1/2}; \tag 3$
we have
$\dfrac{\partial \sigma}{\partial t} = \dfrac{1}{2}((p(t) - q(s)) \cdot (p(t) - q(s)))^{-1/2}(p'(t) \cdot (p(t) - q(s)) + (p(t) - q(s)) \cdot p'(t))$ $= ((p(t) - q(s)) \cdot (p(t) - q(s)))^{-1/2}(p'(t) \cdot (p(t) - q(s))), \tag{4}$
and
$\dfrac{\partial \sigma}{\partial s} = \dfrac{1}{2}((p(t) - q(s)) \cdot (p(t) - q(s)))^{-1/2}(-q'(s) \cdot (p(t) - q(s)) + (p(t) - q(s)) \cdot -q'(s))$ $= ((p(t) - q(s)) \cdot (p(t) - q(s)))^{-1/2}((-q'(s) \cdot (p(t) - q(s))); \tag{5}$
the point $(t, s)$ is thus stationary for $\sigma$ if and only if
$((p'(t) \cdot (p(t) - q(s)) = ((q'(s) \cdot (p(t) - q(s)) = 0; \tag{6}$
we note that the tangents to $p(t)$ and $q(s)$ are $p'(t)$ and $q'(s)$, respectively. Thus $p(t) - q(s)$ is a common normal vector to these curves at $(t, s)$; likewise, if $p(t) - q(s)$ is a common normal vector, (6) binds, hence
$\dfrac{\partial \sigma(t, s)}{\partial t} = \dfrac{\partial \sigma(t, s)}{\partial t} = 0, \tag{7}$
and $(t, s)$ is stationary for $\sigma$.
HINT: Suppose one curve is given parametrically by $\mathbf f(s)$ and the other by $\mathbf g(t)$. What does it mean for $(s_0,t_0)$ to be a critical point of the function $$\phi(s,t) = \|\mathbf f(s)-\mathbf g(t)\|^2 = \big(\mathbf f(s)-\mathbf g(t)\big)\cdot\big(\mathbf f(s)-\mathbf g(t)\big)?$$ (Note that the chord joining $\mathbf f(s)$ and $\mathbf g(t)$ has direction vector $\mathbf f(s)-\mathbf g(t)$.)
