Considering this post pushed me in the right direction for solving this exact problem for an assignment, I figured I should share my solution for any future students with the same problem. Assume all vector spaces are over the scalar field $\mathbb F$.
For every $(s,t)\in S\times S$ choose $\psi_{s,t}:X^*\to \mathbb F$ such that
$$\psi_{s,t}(\phi)=\begin{cases}
\frac{\phi(f(s)-f(t))}{d(s,t)} & s\neq t \\ 0 & s=t
\end{cases}$$
for each $\phi \in X^*$. I leave it to the reader to prove that each $\psi_{s,t}\in X^{**}$.
I claim that for each $\phi \in X^*$ the set $\{\psi_{s,t}(\phi):(s,t)\in S\times S\}$ is bounded. To prove this fix some $\phi \in X^*$. For all $s\in M$ it is trivial to see that $|\psi_{s,s}(\phi)|=0$. Now, for any $\psi_{s,t}$ such that $s\neq t$,
\begin{align*}
|\psi_{s,t}(\phi)|& = \left|\frac{\phi(f(s)-f(t))}{d(s,t)}\right| \\
%
& = \left|\frac{\phi(f(s))-\phi(f(t))}{d(s,t)}\right| \\
%
& \leq \frac{C_\phi d(s,t)}{d(s,t)}=C_\phi,
\end{align*}
where $C_\phi$ is the Lipschitz constant guaranteed by the assumption, depending only on $\phi$. Hence the claim is proved. The Principle of Uniform Boundedness thus guarantees a positive real number $K$ such that $\|\psi_{s,t}\|_{X^{**}}\leq K$ for all $(s,t)\in S\times S$ $(\dagger)$. We can use the PUB because $X^*$ is always a Banach space.
We now need a common theorem in functional analysis (see Theorem 4.3-3 in Kreyszig) that states that for any nonzero $x\in X$ there exists a $\phi \in X^*$ such that $\phi(x)=\|x\|_X$ and $\|\phi\|_{X^*}=1$.
If $f(s)=f(t)$ it is easy to see that these elements satisfy the Lipschitz condition. So if $f(s)\neq f(t)$ we get a $\phi\in X^*$ satisfying the conditions in the above theorem. This, our definition, and $(\dagger)$ give that $$\|f(s)-f(t)\|_X=|\phi(f(s)-f(t))|=d(s,t)|\psi_{s,t}(\phi)|\leq Kd(s,t).$$