How to prove finding two paths that are at least k edges apart is NP-hard?
You can reduce from 3SAT.

The graph has two parts. One part is the "variable" part. For each of the variables $v_1,\ldots,v_n$ there are two three vertices $v_i^+,v_i^-,v_i$, and this part consists of the following edges, for $i \in [n]$:

$$(v_{i-1},v_i^+),(v_{i-1},v_i^-),(v_i^+,v_i),(v_i^-,v_i)$$

Here $v_0$ is a new vertex, identified with $s_1$, and $v_n$ is identified with $t_1$.

The second part is the "clause" part. For each of the clauses $C_1,\ldots,C_m$ there four vertices $w_j^1,w_j^2,w_j^3,w_j$, connected much as before, with $s_2$ and $t_2$.

We connect $v_i^b$ with $w_j^r$ via a path of length $k$ (for some large enough constant $k$) if the literal $v_i^b$ (either $v_i$ or $\overline{v_i}$, according to $b$) is the opposite of $j$'th literal in $C_j$.

Also, we take all the mindpoints of these paths, and connect all of them (making them into a clique).

We can think of an $(s_1,t_1)$-path as a truth assignment, and of an $(s_2,t_2)$-path as identifying a satisfied literal in each clause. The minimal distance is more than $k$ if this is indeed the case, and only $k$ otherwise. 

You also need to verify that there is no point for the paths to cross between the parts. If only one of the paths crosses, then the two paths will be close together (at some constant distance, which for large enough $k$ will be smaller than $k$) immediately after the crossing. If both cross, then the midpoint clique will ensure that they are at distance at most 1.