Minimum amount of time for two enemies to reach their destinations?
Generate the graph $G'$ of all legal configurations. A legal configuration is an ordered pair of vertices $\langle u, v \rangle$ in $V^2$ such that $d_G(u,v) \ge k$, where $d_G(u,v)$ denotes the distance between $u$ and $v$ in $G$.

There is an edge from $\langle u_1, v_1 \rangle$  to $\langle u_2, v_2 \rangle$ in $G'$ if and only if $d_G(u_1, u_2) \le 1$ and $d_G(v_1, v_2) \le 1$.

The amount of time you are looking for is now equal to $d_{G'}(\langle s_x, s_y \rangle, \langle t_x, t_y \rangle)$.