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.
By [G, Theorem 1.10 (Hopf-Rinow)], the closed metric balls of $X$ are compact. Let $(U_k)_{k\geq0}$ be a countable basis of $X$. 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$; for instance, 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).