The following argument works as long as $f_w$ is injective. The same ideas should also work for general $f_w$. Indeed, below I show how they give a bound $|w| \leq O(n!)$. However, even further down I show a much better bound, $|w| \leq e^{2(1+o(1))\sqrt{n\log n}}$, which is tight up to the constant $2$.
Consider some word $w$ which is the minimal length word resulting in $f_w$, and suppose that the range of $f_w$ is $Q$. We want to show that $|w| \leq n!$.
Let $w_{\leq i}$ denote the prefix of $w$ of length $i$. If $f_{w_{\leq i}} = f_{w_{\leq j}}$ for some $i < j$ then $f_{w_{\leq i} w_{>j}} = f_w$, contradicting the assumption that $w$ has minimal length. We conclude that $f_{w_{\leq i}}$ is different for all $i$. Since the range of $f_w$ is full, all $f_{w_{\leq i}}$ must be permutations of $Q$. Since there are $n!$ permutations of $Q$, we conclude that $|w| \leq n!-1$.
Suppose now that $f_w$ is not injective, and write $w = x_1\ldots x_k$, where each step passing from $x_i$ to $x_{i+1}$ decreases the image. The same argument as before shows that $|x_1| \leq n!$, $|x_2| \leq n!/1!$, $|x_3| \leq n!/2!$, and so on. In total, we get that $|w| \leq n!(1+1+1/2+1/6+\cdots) \leq e n!$.
We can do slightly better. For example, if $f_{x_1}(q_1) = f_{x_2}(q_2)$ then when bounding $x_1$, it is enough to consider permutations up to a permutation of the images of $q_1$ and $q_2$, and so when $k \geq 2$ we can conclude that $|x_1| \leq n!/2$. This argument probably gives $|w| \leq (3/2)n!$. One can probably push the argument further, but that would require looking across the boundaries of the segmentation $w=x_1\ldots x_k$.
The following construction shows that $n!-1$ cannot be replaced by anything smaller than roughly $e^{\sqrt{n\log n}}$. Landau's function $g(n)$ is the maximal order of an element in $S_n$. It is known that $g(n) = e^{(1\pm o(1))\sqrt{n\log n}}$. Given an element $\pi \in S_n$ of maximal order, we can construct an automaton over the one language alphabet $\{a\}$ in which $Q = \{1,\ldots,n\}$ and $f_a = \pi$. The word $a^{g(n)-1}$, which generates the permutation $\pi^{-1}$, cannot be shortened.
Consider again the case of injective $f_w$. We can think of the letters of $w$ as generating a subgroup of $S_n$. Babai and Seress show that the diameter of the corresponding Cayley graph is at most $e^{(1+o(1)) \sqrt{n\log n}}$. This means that every permutation in the subgroup, including $f_w$, can be written as a word over the letters of $w$ and their inverses of length at most $e^{(1+o(1)) \sqrt{n\log n}}$. Since the order of each permutation is at most $e^{(1+o(1))\sqrt{n\log n}}$, we can replace the inverse of each letter by at most $e^{(1+o(1))\sqrt{n\log n}}$ copies of itself, obtaining a word of length $e^{2(1+o(1))\sqrt{n\log n}}$. This bound can perhaps be improved by looking at the construction of Babai and Seress.
In the general case, segment $w=x_1\ldots x_k$ as before, where $k \leq n$. A similar argument shows that $|x_i| \leq e^{2(1+o(1))\sqrt{n\log n}}$, and so $|w| \leq e^{2(1+o(1))\sqrt{n\log n}}$.
This still leaves open the value of the smallest $\ell(n)$ such that the minimal word $w$ with given $f_w$ has length at most $\ell(n)$. Our arguments show that $e^{(1+o(1))\sqrt{n\log n}} \leq \ell(n) \leq e^{2(1+o(1))\sqrt{n\log n}}$, leaving a small gap.
