This problem is $NP$-complete. Reduce from Exact Cover by $3$-Sets (X3C).
Given an X3C instance, its ground set is $\mathcal{U}=\{e_1,e_2,\cdots,e_n\}$. Its collecion of $3$-subsets is $\mathcal{C}=\{s_1,s_2,\cdots,s_m\}$.
For each element in the ground set and each subset in the collection,
we create a new vertex (which will be referred to by the same name,
henceforth).
For each pair of element $e_i$ and subset $s_j$ such that $e_i\in s_j$, connect the two
vertices.
For $s_j$'s vertices:
Connect all pair of $s_j$'s vertices to make these a clique.
Then, create a new vertex $s$ and connect it to all $s_j$'s vertices.
For $e_i$'s vertices: For each pair of elements $e_{i_1}, e_{i_2}$ that share no
common subset, we create a new vertex $e_{i_1i_2}$ and connect it to both of
$e_{i_1}$ and $e_{i_2}$.
Then, create a new vertex $e$ and connect it to all $e_{i_ai_b}$'s vertices.
Connect $s$ and $e$ by an edge. Create a new vertex $t$ and connect it
to both of $s$ and $e$.
Call the newly constructed graph $G$. Set $k=\frac n3+1$.
Clearly, we only need to decrease the distance from $t$ to each of $e_i$'s vertex.
If in the planted clique, we do not choose $t$, then for each $e_i$, we need to connect it to either $s$ or $e$. Because $s$ and $e$ are all the neighbors of $t$. That is going to exceed the bound of $\frac n3+1$ on the cardinality of the clique.
So, $t$ must be included in the planted clique. Denote by $x$, $y$ and $z$ (in this order) the number of vertices included in the planted clique among the $s_j$'s vertices, $e_i$'s vertices and $e_{i_ai_b}$'s vertices (resp.)
We can see that each one in $x$ vertices of $s_j$'s vertices will decrease the distance from $t$ to $3$ $e_i$'s vertices.
Similarly, each one in $y$ vertices of $e_i$'s vertices will decrease the distance from $t$ to $1$ $e_i$'s vertices.
And, each one in $z$ vertices of $e_{i_ai_b}$'s vertices will decrease the distance from $t$ to $2$ $e_i$'s vertices.
So, we must have $3x+y+2z\geq n$. But also, $x+y+z=\frac n3$.
We deduce that $x=\frac n3$ and $y=z=0$
