If $(X,d)$ is a complete metric space with the algebraic midpoint property (i.e. for all $x$ and $y$ in $X$, there exists $z\in X$ such that $d(x,z)=d(y,z)=d(x,y)/2$) then $X$ is a path metric space. Indeed, for all $x,y\in X$ one can iteratively construct a map $\gamma$ from $[0,1]\cap\mathbb D$ to $X$ such that $d(\gamma(s),\gamma(t))=|t-s|$, and extend it using completeness of $X$. Here $\mathbb D$ is the set of dyadic numbers. This result is Theorem 1.8 in [G].

Suppose that $(X,d)$ is complete, locally compact, and has the algebraic midpoint property. Then $X$ has the measurable midpoint property.

Of course, this does not include general closed convex subsets of Banach spaces, but it covers for instance any complete manifold.

Let us $(U_k)_{k\geq0}$ construct a countable basis of $X$; in particular, it will show that $X$ is second countable. I want the diameter of $U_k$ to tend to zero as $k$ goes to infinity, and every fixed $x$ to be contained in an infinite number of $U_k$. By [G, Theorem 1.10 (Hopf-Rinow)], the closed metric balls of $X$ are compact; then one can take a finite open cover of $B(x_0,1)$ by open balls of radius $1/1$, then a finite open cover of $B(x_0,2)$ by open balls of radius $1/2$, etc. Let also $(z_k)_{k\geq0}$ be a sequence such that $z_k\in U_k$.

Note that for any closed set $F$, the set of pairs $(x,y)$ such that $F$ contains at least one midpoint of $\lbrace x,y\rbrace$ is closed, using the compacity of closed bounded sets. Let $k_0(x,y)$ be the first $k$ such that the closure $\overline U_k$ contains at least one midpoint of $\lbrace x,y\rbrace$, and iteratively $k_{n+1}(x,y)$ is the first $k>k_n(x,y)$ such that the closed intersection
$$ \overline U_k\cap\bigcap_{0\leq m\leq n}\overline U_{k_m(x,y)} $$
contains at least one midpoint of $\lbrace x,y\rbrace$.

Note that $k_n(x,y)$ is measurable, since the set of $(x,y)$ such that $k_n(x,y)\leq K$ is a finite union of closed sets. Then obviously $f_n:(x,y)\mapsto z_{k_n(x,y)}$ is measurable as well. Since the diameter of $U_k$ tends to zero, $(f_n(x,y))_{n\geq0}$ is a Cauchy sequence for all $(x,y)$, and $f(x,y):=\lim_{n\to\infty}f_n(x,y)$ is a well-defined midpoint of $\lbrace x,y\rbrace$. As a limit of measurable functions, it is measurable as well.

[G] *M. Gromov,* Metric structures for Riemannian and non-Riemannian spaces. 3rd printing (2007).