More generally, for any closed subset $S$ of a complete manifold $M$, the set of points $x$ at whose minimal distance to $S$ is attained at more than point has measure $0$.
Indeed, consider the distance function $f:M\to\mathbb{R}$ given by $d_S(x)=d(S,x)$. Then $d_S$ is $1$-Lipschitz, so by Rademacher's theorem it is almost everywhere smooth. It will thus be enough to prove that:
Claim: If $f$ is smooth at some point $p\not\in S$, then there can be at most one point $s\in S$ minimizing distance to $p$.
Proof: First note that the derivative of $f$ at $p$, $df_p:T_pM\to\mathbb{R}$, has norm $1$ because $p$ is $1$-Lipschitz. Now, choose some $s\in S$ such that $d(p,s)=f(p)$ (that is, $s$ minimizes distance to $p$). Let $\gamma:\mathbb{R}\to M$ be a unit speed geodesic with $\gamma(0)=p,\gamma(f(p))=s$, and let $v=\gamma'(0)$. Then we have
$$df(v)=\left.\frac{d}{dt}\right|_{t=0}(f(\gamma(t)))\leq\left.\frac{d}{dt}\right|_{t=0}(d(\gamma(t),s))=\left.\frac{d}{dt}\right|_{t=0}(f(p)-t)=-1.$$
In fact $df(v)=-1$, because $f$ is $1$-Lipschitz so $df|_p$ is $1$-Lipschitz too. If there were another point $s'\in S$ at minimal distance from $p$, we would also have $df(v')=-1$ (where $v'$ is a tangent vector pointing to $s'$ as above). Moreover, we would have $v'\neq v$, as the points $s,s'$ are determined by the vectors $v,v'$ due to uniqueness of geodesics: $\exp(f(p)v)=s\neq s'=\exp(f(p)v')$. So it is enough to check that there is just one vector $v\in T_pM$ such that $df(v)\leq-1$. We prove that in the claim below.$\square$
Subclaim: For any Hilbert space $H$ over $\mathbb{R}$ and any linear map $L:H\to\mathbb{R}$ with $|L|\leq1$, there can be at most one unit vector $v$ such that $L(v)=-1$.
Proof of subclaim: Note that, as $L$ is $1$-Lipschitz, $|L(v)|$ is at most the distance from $v$ to ker$(L)$. But the codomain of $L$ has dimension $1$, so ker$(L)$ has codimension $\leq1$. Thus, there can be at most two unit vectors at distance $1$ of ker$(L)$: the two unit vectors orthogonal to ker$(L)$. Those are the only two unit vectors $v$ which may satisfy $L(v)=-1$, and as they are opposite, $L$ cannot be $-1$ in both of them.$\square$
Also, if $M$ is not complete (I assume we are still giving $M$ the length metric) then $P_S$ may have positive measure, e.g. let $M=\{(x,y)\in\mathbb{R}^2;x>0\text{ or }y>0\}$ and let $S$ be a curve contained in $\{(x,y)\in\mathbb{R}^2;x<0,0<y\leq|x|\}$ such the $\mathbb{R}^2$-distance from $(0,0)$ to $S$ is minimized at more than one point. Then, all points $(x,y)$ such that $x>0$ and $y\leq -x$ are contained in $P_S$.