The answer is either $\mathbb{N},\{0,1\},\{0,1,2\}$ or $\{0,1,2,3\}$. The first is easily achievable with $E=\{(x,x+1)|x\in \mathbb{N}\}$. The second one is achievable with the complete graph on $\mathbb{Z}$. The third one is achievable with the complete bipartite graph on $2\mathbb{Z}+1$ and $2\mathbb{Z}$. The fourth and final possibility is achievable with $E=\{(x,y)| x-y\equiv \pm 1\pmod 6\}$. It is easy to check that all of these work out. To prove they are the only one, note that if $d\in S(G)$ and $0\leq d'<d$ then $d'\in S(G)$. This is because we can take two points with distance $d'$ on a path of length $d$ (which connects two points at distance $d$). Therefore $S(G)$ is either $\mathbb{N}$ (i.e. the nonnegative integers) or $[0,m]\cap \mathbb{Z}$, with $m\geq 1$. Now, if $m\geq 4$, it follows there are two points $x,y$ at distance $4$, implying that $4|x-y$, i.e. $x-y=4t$ for some nonzero integer $t$. Lemma: for all even numbers $d$ and for all $M>1$ there exist two numbers $a,b$ such that $(a,M)=(b,M)=1$ and $a-b=d$. Proof: it suffices to find two such numbers $\pmod M$, and in particular it suffices to do so mod every prime power of $M$ $p^k$. If $p=2$, just choose $1$ and $1+d$. If $p>2$, it must always be true that one of $(1,d+1),(2,d+2)$ works, because $p\nmid 1,2$ and it also can't divide both $d+1$ and $d+2$. Returning to our problems we note that if $M=m!$ (which is an even number) and $(a-b,M)=1$ then $d(a,b)|m!$ and $d(a,b)|a-b \implies d(a,b)=1$. So choosing some two numbers $a,b$ such that $a-b=4t$ and $(a,M)=(b,M)=1$, we can choose the point $z=x+b=y+a$ which has difference $b$ from $x$ and $a$ from $y$. Therefore $d(z,x)=1$ and $d(y,z)=1$, which implies $d(x,y)\leq d(x,z)+d(x,y)=2$, in contradiction with $d(x,y)=4$.

well @cadaeibf I do not get your lemma I think it has some problem could you make a more detailed explanation?

Answers are $S\equiv Z^+,S=\{1\},S=\{1,2\},S=\{1,2,3\}$ since $d(z,y)\neq 0$. Constructions are same as above. Let $T_i$ be the set of vertices $d(1,v)=i$. We observe that $d(1,p+1)\in \{1,p\}$. Note that $T_i$ and $T_j$ don't have connected vertices if $i-j>1$. We split into two cases. Case $I$: If there are infinitely many primes $p$ with $d(1,p+1)=p$. Choose some vertex $v\in T_i$. Since the shortest path between $v$ and sufficiently large $p+1$ is $p-i$ hence $p-i|p+1-v$ or $p-i|i+1-v$ however $p-i$ goes to infinity thus, $v=i+1$ which implies $S\equiv Z^+$. Case $II$: If there are finitely many primes $p$ with $d(1,p+1)=p$, then $d(1,p+1)=1$ for some $p\geq M$. Suppose that $v\in T_i$ with $i\geq 4$. Note that $p+1\in T_1$ for $p\geq M$. We must have $i-1|p+1-v$ and by Drichlet, we can choose $p_1\equiv -1(mod \ i-1)$ and $p_2\equiv 1(mod \ i-1)$ which would imply $i-1|v$ and $i-1|v-2$ is a contradiction. Thus, we have at most $T_1,T_2,T_3$. Let's show that $d(x,y)\leq 3$. If there are just $1,T_1$ then $d<3$. If there are only $1,T_1,T_2$ then odds and evens in $T_1$ have $\leq 2$ distance howevere their difference is odd which yields each pair of odd and even are directly connected. If $u,v\in T_2$ then any of these vertices cannot be in $1,T_1$ since $d(1,x)\leq 2$ and $d(u_1,v_1)\leq 2$ for $u_1,v_1\in T_1$. Thus, both $u,v$ must be in $T_2$. We see that $2|u_2-1$ for $u_2\in T_2$ hence all numbers in $T_2$ are odd. This implies that all evens are in $T_1$. If $u$ is not connected to some even, then $l|u-e$ for any even $e$ and some $l\geq 3$ but this is impossible. So both $u,v$ are connected to some evens. Choose an even number $E\not \equiv u,v(mod \ 3)$. If $E,u$ are not connected, then $u-e_1-o_1-E$ is the shortest path between $u,E$ which is impossible. Similarily $E$ is connected to $v$ thus, $d(u,v)\leq 2$. Now suppose that all $1,T_1,T_2,T_3$ exist. Also assume that $d(u,v)>3$. Similarily odds and evens in $T_1$ are directly connected. We have $d(1,x)\leq 3$. Also a member of $T_1$ has distance less than $4$ to a member of $T_2\cup T_3$. If at least one of $u,v$ is in $T_2$ then their distance would be at most $4$. Suppose that it's $4$ which implies $u,v$ have the same parity. WLOG $u\in T_2$. $u,v$ must be odd. Also $v\equiv 1(mod \ 3)$. This yields each even in $T_1$ must be $\equiv 1(mod \ 3)$. However there cannot be $2(mod \ 6)$ numbers in any of $1,T_1,T_2,T_3$ which is impossible. So we must have $u,v\in T_3$. We observe $d(u,v)\leq 5$. If $d(u,v)=5$, then there is an edge in $T_1$ which connects an odd vertex and an even vertex on their shortest path however this is impossible by parity. Suppose $d(u,v)=4$. Let the path be $u-k-m-l-v$. Also $k,l$ are not connected. We see $k,l\equiv 1(mod \ 3)$ bt looking at $d(u,l)$ and $d(v,k)$. If there is no even $m$ satisfying the conditions, then each even in $T_1$ must be $\equiv 1(mod \ 3)$ but this yields there is no $2(mod \ 6)$ number in any of these groups. Thus, there exists an even $m$. $u,v$ must be even so $k,l$ are not connected to an odd in $T_1$. If $w\in T_2$ is not connected to an even in $T_1$, then $2|w-e$ but $w$ is odd hence each number in $T_2$ is connected to an even number in $T_1$. Consider a $N\equiv 5(mod \ 6)$ number. $N$ cannot be in $T_1,T_3$ hence $N\in T_2$. $N$ is not connected to both $u,v$. WLOG $N,u$ be unconnected. $N-e-k-u$ is the shortest path between them thus, $3|N-u$ however $N\equiv 2(mod \ 3)$ while $u\equiv 1(mod \ 3)$ which is a contradiction as desired.$\blacksquare$