Let $G$ be a (discrete) group. Define $k^*(G)$ as the minimal cardinality of a set $S \subset G$ such that $C_G(S) = Z(G)$. Define $k(G) = k^*(G)$ if $G$ has trivial center (i.e. $|Z(G)| = 1$), and $k(G) = \bot$ otherwise. If $k(G) = \bot$, then the convention is that neither $k(G) \leq n$ nor $k(G) \geq n$ holds, for any cardinal $n$.

Question: Does there exist a finite group $G$ such that $k(G) \geq 3$, and more generally does every natural number $k(G) \geq 3$ occur for some finite group $G$?

I do not even know such examples for $G$ infinite, and would also be interested in such, though I do not have an immediate application for this. I am not an expert on group theory (especially finite group theory), so I do not know very effective search terms for this, and would also be interested in pointers to the literature.

What I have tried so far (though don't take my word on these):

No abelian group or a p-group or a nilpotent group is an example, since they have nontrivial centers (in the finite case), thus $k(G) = \bot$.

No finite simple group is an example, since they are all 2-generated (by CFSG), thus satisfy $k(G) \leq 2$ or $k(G) = \bot$.

$k(G \times H) = \max(k(G), k(H))$ for any groups $G, H$ (by a simple proof).

I did a quick search in GAP and seems that there are no finite groups of size up to $1151$ with this property (this is the first time I used GAP, so not sure how much proof value this has).

$k(G) = 0$ for precisely the trivial group, and $k(G) = 1$ is impossible (since any $g$ commutes with itself).

For infinite cardinal $\kappa$, $k(G) = \kappa$ where $G$ is the group of finite-support permutations on a set of cardinality $\kappa$, but of course $k(G)$ is finite (or $\bot$) for finite groups.

Arbitrarily large $k^*(G)$ are provided by wreath products $\mathbb{Z}_2 \wr \mathbb{Z}_2^d$, where $\mathbb{Z}_2 = \mathbb{Z}/2\mathbb{Z}$, but I wrote a quick proof sketch that $k(G \wr H) = 2$ whenever $|H| \geq 2$ and $k(G) = 2$ so it seems one cannot use wreath products to get examples.

For a single permutation $\pi$ on a set of size $n$, The centralizer of $\pi$ in $S_n$ never has $k(G) \geq 3$ (I prove this as Proposition 7.9 in this paper of mine, by a rather ad hoc case analysis).

In terms of the commuting graph $\Gamma(G)$ with vertices $G \setminus Z(G)$ and edges $\{(g, h) \;|\; gh = hg\}$, the question of whether $k(G) \geq 3$ is possible is equivalent to whether there exists a finite group $G$ with trivial center such that $\mathrm{diam}(\Gamma(G)) = 2$, where $\mathrm{diam}$ is the diameter, i.e. maximal minimal distance between a pair of vertices. For a finite minimal nonsolvable group the diameter is always at least $3$ according to this paper which implies $k(G) = 2$ for a minimal nonsolvable group (a different definition is used in that paper, but it should be equivalent to mine for minimal nonsolvable groups, as they have trivial center). Most literature I know about this graph and its diameter are about finding upper bounds, but I do not know if that has a relation to $k(G)$. Larger values of $k(G)$ also correspond to statements about this graph, but not about its diameter.

For context, the question arose from the study of automorphism groups of one-dimensional subshifts. I am interested in quantitative versions (or lack thereof) of the so-called Ryan's theorem, which states that the center of the automorphism group of a mixing subshift of finite type consists of only the shift maps. I ask the above question about finite groups after Lemma 7.7 here and Lemma 7.7 is my application for it. The paper of Boyle, Lind and Rudolph is a standard reference for these groups.