The answer is no.
Define the manifold
Let $f$ be a smooth function on $\mathbb{R}$ satisfying
- $f(r) = |r|$ for $|r| > 3$
- $f(r) > 0$
- $f''(r) \geq 0$.
The corresponding warped product metric on $\mathbb{R}^2$
$$ \mathrm{d}s^2 = \mathrm{d}r^2 + f(r)^2 \mathrm{d}\theta^2 $$
is complete and has non-positive curvature. The exterior regions $|r| > 3$ are flat. It is in fact the simply connected cover of a corresponding warped metric on $\mathbb{R}\times\mathbb{S}^1$, which when $|r| > 3$ are two copies of the Euclidean plane with a ball removed.
Since geodesics (lines) in the Euclidean plane are confined to a half plane, we know that geodesics satisfying $|r(\gamma)| > 3$ must have bounded $\theta$ within some $[\theta_0, \theta_0+\pi]$. In other words, for a lot of what we are going to say we can just work in the quotient picture, without worrying too much about the lift to upstairs.
Counterexample
In the quotient picture fix, in rectangular coordinates on $\mathbb{R}^2 \setminus B_3(0)$ a point $(x,y)$ in the first quadrant, such that
- $x> y > 3$
- the line $\tilde{\gamma}: t\mapsto (x-t/\sqrt{2}, y-t/\sqrt{2})$ does not enter the ball of radius 3.
Let $o = (x,y)$ (or rather its lift to our manifold defined above), and $a = (x,0)$, $b = (y,0)$.
Notice that $\tilde{\gamma}$ is geodesic. Note also that we don't have to worry about the quotient/lift since $L_a, L_b$ and $\tilde{\gamma}$ all avoid the "cut" at $\{x = y \wedge x,y < 0\}$.
Note further that for some $\epsilon$ time that $\tilde{\gamma}(t)|_{t\in (-\epsilon,\epsilon)} = m(t)$.
Note also that $\tilde{\gamma}(t)$ always stay on the "$L_a$ side" of the "hole"
But this does not hold for all times: once the geodesic segment joining $L_a(t)$ to $L_b(t)$ starts to enter the ball of radius 3, its midpoint would start to deviate from $\tilde{\gamma}$, and move closer toward $L_b(t)$.
This is easiest to see when $t$ is very very large. When $t$ is very very large, on the original manifold, the geodesic connecting $L_b(t)$ to $L_a(t)$ must first go into the hole, which requires travelling distance approximately $t - y + O(1/t)$, and exit the hole, and reach $L_a(t)$, traveling another distance that is approximately $t-x + O(1/t)$. The distance traveled in the hole is $\leq 6\pi$. So asymptotically the midpoint $m(t)$ remains in fact in a compact region of our manifold. If initially $y$ is much smaller compared to $x$ (in the sense that $x-y > 6\pi$), in fact we expect $m(t)$ to appear "on the other side of the hole" eventually.
Since $m(t)$ and $\tilde{\gamma}(t)$ coincide for some time interval, but their image do not coincide globally, we conclude that $m(t)$ cannot be always a local geodesic.