Let $S_n$ be the permutation group and $V = \operatorname{Fun}(X,\mathbb{k})$ functions from $X=\{1,\dotsc,n\}$ to some field $\mathbb{k}$. How can I prove that every irreducible representation of $S_n$ occurs in $V^{\otimes m}$ for integer $m$ large enough?
This is a standard fact when $n!\neq 0$ in $\mathbb{k}$.
Turning my comment into an answer, Robert Steinberg proved in Complete sets of representations of algebras that if you have a faithful representation of a finite semigroup $S$, then every irreducible representation of $S$ appears as a composition factor of a tensor power of that representation. In fact, he shows that the semigroup algebra $KS$ acts faithfully on the direct sum of the tensor powers, which is a stronger statement since finite semigroups are not usually completely reducible. My favorite proof of this is Passman’s variant of a proof of Rieffel in Elementary bialgebra properties of group rings and enveloping rings: An introduction to Hopf algebras.
If $G$ is a finite group, then $KG$ is a Frobenius algebra and so every irreducible representation is a subrepresentation of the regular representation. Thus in the case of a finite group, every irreducible representation will be a subobject of a tensor power.
For semigroups, this is not true. There are many examples. The easiest is the monoid $T_n$ of all maps on $n$ letters. For $n\geq 2$, the natural representation on $\mathbb C^n$ is faithful and has the trivial representation as a quotient but not as a subrepresentation. The same remains true after taking tensor powers.
Benjamin Steinberg answered the question, but I wanted to unwind his idea into an explicit formula.
Let $V$ be the representation with basis $e_1,\dotsc, e_n$, where a permutation $\sigma$ acts by sending $e_i$ to $e_{\sigma(i)}$.
Let $W$ be an irreducible representation of $S_n$.
Fix a linear form $l$ on $W$. We can map $W$ to $V^{\otimes n}$ by sending $w \in W$ to $$f(w) = \sum_{ \sigma \in S_n} l ( \sigma^{-1} (w))\cdot e_{\sigma (1) }\otimes e_{\sigma(2)} \otimes \dotsm\otimes e_{ \sigma(n) }.$$
Then we have \begin{align*} \sigma' (f(w)) & {}= \sum_{ \sigma \in S_n} l ( \sigma^{-1} (w))\cdot \sigma'( e_{\sigma (1) }\otimes e_{\sigma(2)} \otimes \dotsm e_{ \sigma(n) } ) \\ & {}= \sum_{ \sigma \in S_n} l ( \sigma^{-1} (w))\cdot e_{ \sigma'(\sigma(1))} \otimes e_{ \sigma'(\sigma(2))} \otimes \dotsm \otimes e_{ \sigma'(\sigma(n))} \\ & {}= \sum_{ \sigma \in S_n} l ( (\sigma' \circ \sigma)^{-1}( \sigma'(w)))\cdot e_{ \sigma'(\sigma(1))} \otimes e_{ \sigma'(\sigma(2))} \otimes \dotsm \otimes e_{ \sigma'(\sigma(n))} \\ & {}= \sum_{ \sigma \in S_n} l ( \sigma^{-1} (\sigma' (w) ))\cdot e_{\sigma (1) }\otimes e_{\sigma(2)} \otimes \dotsm\otimes e_{ \sigma(n) } = f(\sigma' (w)) \end{align*} using the change of variables $\sigma \mapsto \sigma' \circ \sigma$ in the last line. So $f$ is a homomorphism, and because $W$ is irreducible, and $f$ is nontrivial (as long as $l$ is a nontrivial linear form, since all the terms in the sum give different basis vectors in the tensor product), this map is the inclusion of a subrepresentation, as desired.
One can get embeddings into $V^{\otimes m}$ for higher values of $m$ by just putting repetitions in the sequence of basis vectors being tensored, or for $n-1$ by removing the last term, but one can't go lower than $n-1$, because of the sign representation (except maybe in characteristic $2$, I guess).
