Added later. I'm adding a proof outline upon a request from comments.
Fix $p\in \mathbb R^n$ and $v\in\mathbb Z^n$. Define $f:\mathbb Z_+\to\mathbb R$ by $f(m)=d(p,p+mv)$. Note that $ \|v\|_{st} = \lim_{k\to\infty} f(k)/k$. The function $f$ satisfies the following properties:
(1) $f(m_1+m_2)\le f(m_1)+f(m_2)$
(2) $f(2m)\ge 2f(m)-C$,
where $C$ depends only on the metric (and in fact equals $C(n)diam(g)$). These properties immediately imply that $k\|v\|_{st}\le f(k)\le k\|v\|_{st}+C$ with the same $C$. For $k=1$, this gives us the desired estimate on $d(p,p+v)=f(1)$.
The property (1) is just the triangle inequality. The property (2) is based on the following topological lemma:
Lemma. Let $s:[0,1]\to\mathbb R^n$ be a continuous path. Then there is a collection of disjoint intervals $[a_i,b_i]\subset[0,1]$, $i=1,2,\dots,k\le (n+1)/2$, such that
$$
\sum (s(b_i)-s(a_i)) = \frac{s(1)-s(0)}2 .
$$
Let me derive property (2) from the lemma. Apply the lemma to a shortest path $s$ connecting $p$ to $p+2mv$. This gives us a collection of at most $n/2$ vectors $v_i=s(b_i)-s(a_i)$ in $\mathbb R^n$ whose sum equals $mv$. Let $p_0=p,p_1,\dots,p_k$ be points such that $p_i-p_{i-1}=v_i$. Then $p_k=p+mv$, and each pair of points $p_{i-1},p_i$ is a (possibly non-integer) parallel translation of $a(t_i),b(t_i)$. Due to periodicity, this implies that $d(p_{i-1},p_i)\le d(a_i,b_i)+C_1$ for some constant $C_1$ depending on $g$. I will address this dependence later. Therefore $f(m)=d(p,p_k)$ is bounded by a constant $C_1n$ plus the length of the parts of $s$ covered by the intervals $[a_i,b_i]$.
Consider the complement intervals $[0,a_1]$, $[b_i,a_{i+1}]$, $[b_k,1]$. The corresponding vectors $s(a_1)-s(0)$ etc, also add up to $mv$. Hence the above argument applies to these intervals as well and implies that $f(m)$ is no greater than $C_1n$ plus the remaining part of the length of $s$. One of these two parts is no greater that half of the total length of $s$, hence the result.
The problem is how to control the constant $C_1$ by the diameter only. To do so, one moves the division points $s(a_i)$, $s(b_i)$ to nearby lattice points (losing at most the diameter on each move), then the required parallel translations preserve the distance and the dependence on the metric goes away. But the new collection of vectors no longer sums up to $mv$. So we have to choose those "nearby" lattice points wisely, so that the accumulated error is bounded by the diameter times $C(n)$. This (hopefully) can be done as follows: approximate $s$ by a sequence of lattice points (with distances between neighboring ones at most twice the diameter), then apply the lemma to the Euclidean broken line connecting these points, then move each division point to the next vertex of this broken line. The error in the sum of the resulting vectors has bounded stable norm and this should imply a bound on the metric distance. (I have not worked through this detail yet.)
Proof of lemma. It was discussed in this answer but the Google Book link there died since that (probably some copyright maniac killed it, now it looks as if the volume was never digitized). The proof it the following, Consider the standard unit sphere $S^n$ of points $x\in\mathbb R^{n+1}$ with $\sum x_i^2=1$. To each point $x\in S^n$, associate a partition $0=t_0\le t_1\le\dots t_{n+1}=1$ of $[0,1]$ such that $t_i-t_{i-1}=x_i^2$, and define $f(x)\in\mathbb R^n$ by
$$
f(x) = \sum sign(x_i) (s(t_i)-s(t_{i+1}) .
$$
The resulting function $f:\mathbb S^n\to\mathbb R^n$ is continuous and odd (i.e. $f(-x)=f(x)$). Therefore $f(x)=0$ for some $x$. Now let $[a_j,b_j]$ be the segments of the partition $\{t_i\}$ associated to this $x$, whose corresponding coordinates $x_i$ are positive. If there are too many of them, take the negative ones instead.
