No: a counterexample for a given $k$ and $n$ may be constructed as follows. Take all $k+1$-tuples of elements from the set $\{1, \ldots, n+1\}$ as vertices, and connect two vertices iff their tuples differ in exactly one value. (In other words, the Cartesian product of $k+1$ copies of $K_{n+1}$.) The diameter of this graph is clearly $k+1$: any vertex can be reached from any other through $k+1$ edges by changing the first element of the tuple, then the second, etc., and this is needed for $(1, 1, \ldots, 1) \to (2, 2, \ldots, 2)$. Then for any set of at most $n$ vertices, we can consider each position in the tuple in turn and pick an element that does not appear (which exists since there are $n+1$ elements to choose from yet the $n$ vertices have at most $n$ elements altogether in that position); the tuple with these elements that don't appear in their positions in $S$ has distance $k+1$ from every element of $S$.