The answer is negative.
Take the sphere $S^2$ with the round metric, and cut out the part which is souther than some latitude line which is close to the south pole. (The threshold line also stays out).
We are left with an open Riemannian submanifold $M$.
Any two points in $M$ will be connected via a geodesic. For some pairs of points it will be the "long" part of the usual geodesic in $S^2$ which connects them. (The short minimzing part passes through an area we have deleted).
For such pairs, there will be no connecting minimizing geodesic:
Since $M$ is open, it is a totally geodesic submanifold of $S^2$. Assume such a pair has a minimizing geodesic between them. Then it must be a geodesic $S^2$, hence the long part of a great circle. However, we can clearly find such a pair for which exists a shorter path in $M$, contrdicting the minimality.
In particular, there are points in $M$ which do not have a minimizing path between them. (By the theorem which states any minimizing path is a geodesic).