Let’s for any bijection $f: A \to A$ define its support as $$supp(f) = \{a \in A| f(a) \neq a\}$$
Now, let’s define $S_\infty$ as the group of all bijections $\mathbb{N} \to \mathbb{N}$ with finite support. By Cayley Theorem any finite group is isomorphic to a subgroup of $S_\infty$. Therefore, for any finite group $G$ we can define its Cayley length as
$$len_c (G) = \min \{\sum_{\alpha \in A} |supp(\alpha)| | A \subset S_\infty \langle A \rangle \cong G \}$$
Now, we can define a following function:
$$CL(n) = \max \{len_c(G) | |G| \leq n \}$$
What is the asymptotic of $CL$?
I managed to derive the following two bounds:
$$CL(n) = O(n \log(n))$$
This is because any finite group $G$ has a generating set of size $O(\log(n))$ and the size of supports of permutations, corresponding to each of those generators under left multiplicative action is $n$.
$$CL(n) = \Omega(n)$$
Suppose $p$ is prime. Then $len_c(C_p) = p$. Indeed, all non-trivial elements of $C_p$ have order $p$, any permutation of order $p$ has size of support dividing $p$.
However, I do not know, whether any of those bounds is tight...
Actually, $CL(n) = \Theta(n)$. Proof of $CL(n) = \Omega(n)$ can be found in the body of the question. To prove the bound $CL(n) = O(n)$ we will construct a "good" Cayley representation (a Cayley representation of $G$ is here a collection of permutations that generate a group isomorphic to $G$) for arbitrary group $G$ using the follwing recursive procedure:
Base: if $G \cong E$ then we do not need any permutations at all.
Step: Suppose, we have already done this for all groups of order less than $|G|$ and that for them all our Cayley representations satisfy the additional requirement of all generating permutations of any group $K$ being from $Sym(K)$. Now, suppose $H$ is some maximal normal subgroup of $G$ which is represented py permutations $p_1, ... , p_t$ from $Sym(H)$. Then $\frac{G}{H}$ is a simple group. Thus, as all simple groups are $2$-generated, we can take elements $g_1, g_2$ such that $\langle H \cup \{g_1, g_2\} \rangle = G$. Then $G$ can be represented by permutations $p_1, ... , p_t, (h \mapsto g_1 h), (h \mapsto g_2 h)$ from $Sym(G)$.
Now, let's demonstrate that the length (i.e. the sum of sizes of supports of all generating permutations) of Cayley representation constructed that way does not exceed $4|G|$:
Base: If $G \cong E$, then $0 \leq 4$
Step: If the inequality holds for every group of order less then $G$, then the length of the corresponding presentation for $H$ is $\leq 4|H| \leq 2|G|$. On the other hand the lengths of permutations $ (h \mapsto g_1 h)$ and $(h \mapsto g_2 h)$ are $|G|$ each. Thus the total length of this Cayley representation for $G$ $\leq 4|G|$.
Thus we can conclude, that $CL(n) \leq 4n$.