For simplicity let $k$ be given fixed, and $n$ grows large. We are interested in a small set $M_n={g_1,...,g_m}$ of permutations in $S_n$, s.t for all $a\in S_n$, there is $g_i \in M_n$ with $ag_i$ having at least $k$ fixed points. The question is how large must $M_n$ be asymptotically depending on $k,n$. Another interesting question after we solve this one, is what happens when we force $M_n$ to be a subgroup of $S_n$.
If ones assums $n \geq (k+1)!$ there is the following upper bound which will be proved below after the lower bound)
Upper bound: $m=O((k+1)!nlog(n))$. Note for $k=1$ we also have the clear upper bound of $n$ taking what's genereated by a large circle.
A (sad) lower bound of $m=\theta ((k+1)!)$ also follows in similiar spirit to the upper bound.
Here is also a lower bound of $\lfloor(n/2)\rfloor$ for $k=1$ (and in particular for the rest of the $k$):
We start with the complete bipartite graph with both sides having $n$ elements, each perfect matching corresponds to a matching which says who the left guy goes to in the right. Each $g_i$ kills a set of edges (i.e if in our permutation that edge exists, then multiplying by $g_i$ would lead to a fixed point for the left guy).
Thus what I claim that if you remove a union of any $\lfloor(n/2)\rfloor-1$ perfect matchings off the complete bipartite graph with $n$ vertices on each side, there is still a perfect matching standing. Note that it is possible to use $\lfloor(n/2)\rfloor$ matchings to cover so that we won't be able to find a perfect matching, so this is tight.
Now if we could only use $\lfloor(n/2)\rfloor-1$, then let's see the set that kills Halls condition. Say it is the set $A$ of size $a$. Then it sees a set $B$ of size at most $a-1$. Clearly $a\leq \lfloor(n/2)\rfloor-1$, otherwise $A$ sees everyone after removing the matchings. So we managed to cover the complete bipartite graph $AxB^c$ with $\lfloor(n/2)\rfloor-1$ matchings exhausting $A$. But $B^c$ has size at least $n-(a-1)\geq n- \lfloor(n/2)\rfloor-1+1=n-\lfloor(n/2)\rfloor > \lfloor(n/2)\rfloor-1$, and so $A$ sees all of $B^c$ after removing our matchings,a contradiction.
Here is an upper bound as promised and the other lower bound:
We want a set of $m$ permutations $g_{1},..,g_{m}$, s.t for all permutations $a$, there is $g_{i}$ with $ag_{i}$ having at least $k$ fixed points. Given a fixed $a$, if we pick a random $g$, what is the probability $ag$ has at least $k$ fixed points? Well since choosing $g$ at random is like $a^{-1}g$ at random, we're asking what is the probability a random $g$ has at least $k$ fixed points. It turns out easier to count the other thing, how many permutations have at most $k-1$ fixed points? Well in paricular how many have exactly $s$ fixed points? That's like fixing the $s$ fixed points, and then picking a derangment (no fixed point) on the rest; number of derangments on $n$ elements is (this one by inclusion exclusion) $n!(\sum_{0}^{n}\frac{(-1)^{i}}{i!})$, for large $n$ this is $\sim\frac{n!}{e}$. Thus the number of those with exactly $s$ fixed points is like $\binom{n}{s}\frac{(n-s)!}{e}$. So the number with at most $k-1$ fixed points is: $\sum_{s=0}^{k-1}\binom{n}{s}\frac{(n-s)!}{e}$. Thus our desired probability is $1-\frac{\sum_{s=0}^{k-1}\binom{n}{s}\frac{(n-s)!}{e}}{n!}=1-\frac{1}{e}(\sum_{s=0}^{k-1}\frac{\binom{n}{s}}{n\cdot(n-1)..(n-s+1)})=1-\frac{1}{e}(\sum_{s=0}^{k-1}\frac{\frac{n(n-1)..(n-s+1)}{s!}}{n(n-1)..(n-s+1)})=1-\frac{1}{e}(\sum_{s=0}^{k-1}\frac{1}{s!})=\frac{\sum_{s=k}^{\infty}\frac{1}{s!}}{e}$, this by Taylor approximation is at least (and up to a constant exactly) $\frac{1}{e(k+1)!}$. At last we can get to our problem. We need to union bound over $n!$ guys, so we want $(1-\frac{1}{e(k+1)!})^{m}<\frac{1}{n!}$. If $m=e(k+1)!$ we get roughly $\frac{1}{e}$, so $e(k+1)!(nlogn)$ is what we want and tight (to get the union bound) up to a const. So our answer is that $m=(k+1)!(nlog(n))$ suffices. To get a lower bound we try to flip our heads as usual. Assume we have just $m$, and we take a random element, the probability m catches us is $\frac{1}{e(k+1)!}$, so the probability at least one of them catches us by union bound is at most $\frac{m}{e(k+1)!}$, so $m\geq(k+1)!$ is a bound.