If dependent choice fails then there is a convex complete metric space metric space with two points not connected by a segment. I'm not yet sure about the converse. It seems clear that $\mathsf{DC}_{\omega_1}$ is sufficient to show that arbitrary convex complete metric spaces have segments, so the precise amount of choice needed is something greater than $\mathsf{DC}$ but at most $\mathsf{DC}_{\omega_1}$.
Assume dependent choice is false and let $(T,\sqsubseteq)$ be a tree (i.e., a partial order with the property that for any $a$, $\{b \in T : b \sqsubseteq a\}$ is well-ordered) with no maximal elements and no infinite paths. Let $x_0$ be the unique minimal element of $T$.
Let $T^\ast = \{x_0\} \cup ((T \setminus \{x_0\}) \times (0,1])$. We will define a metric on $T^\ast \cup \{x_1\}$, where $x_1$ is some new element. Define a partial order $\leq$ on $T^\ast$ as follows: $x_0$ is the unique minimal element. For any $(a,r)$ and $(b,s)$, $(a,r) \leq (b,s)$ if and only if either $a\sqsubset b$ or $a=b$ and $r \leq s$. (Basically we've taken the tree $T$ and filled in each line segment between nodes with actual points and extended the partial order in the obvious way.)
It's relatively straightforward to check that under $\leq$, any two elements of $T^\ast$ have a meet (i.e., a greatest lower bound). Let $a \wedge b$ be the meet of any $a$ and $b$ in $T^\ast$.
Now define a height function $h$ on $T^\ast$ as follows: $h(x_0) = 0$. For any $a \in T$ and $r \in (0,1]$,
$$ h((a,r)) = \frac{1}{2} - 2^{-|\{b \in T : b \sqsubset a\}|-1}(2-r).$$
So, for example, if $a$ is a direct child of $x_0$, then $h((a,r)) = \frac{1}{2} - 2^{-1-1}(2-r)= \frac{r}{4}$. If $a \in T$ is an element of height $2$ (i.e., a child of a child of $x_0)$, then $h((a,r)) = \frac{1}{4}+ \frac{r}{8}$. For height $3$, we get $h((a,r)) = \frac{3}{8} + \frac{r}{16}$. Note that the supremum of the values of $h$ is $\frac{1}{2}$.
Now use $h$ to define a metric on $T^\ast \cup \{x_1\}$. For any $y,z \in T^\ast$, we let $d(y,z) = h(y) + h(z) - 2h(y\wedge z)$. It's a little tedious but not hard to show that this satisfies the triangle inequality. For any $y \in T^\ast$, we let $d(y,x_1) = 1-h(y)$. To see that this satisfies the triangle inequality, note that for any $y,z \in T^\ast$, we have that $d(y,z) \leq 1$ but $d(y,x_1) + d(x_1,z) \geq 1$.
Call this metric space $(X,d)$. Note that we clearly do not have a segment between $x_0$ and $x_1$ because no other points are less than distance $\frac{1}{2}$ from $x_1$.
I claim that $(X,d)$ is convex and complete (both in the Cauchy sequence sense and in the Cauchy filter sense). Convexity is relatively straightforward. ($(T^\ast,d)$ is an $\mathbb{R}$-tree, which is always convex. Convexity between $x_1$ and points in $T^\ast$ can be checked directly.) Completeness follows from the fact that for any Cauchy sequence $(y_i)_{i \in \mathbb{N}}$ of elements of $T^\ast$, we must have that there is an $r < \frac{1}{2}$ such that $h(y_i) < r$ for all $i$.
For Cauchy filter completeness one shows that there's a way of converting any given Cauchy filter to a Cauchy sequence converging to the same point. Alternatively one could observe that if a Cauchy filter in $T^\ast$ has unbounded $h$-value, then its limit point would yield a path through $T$.
