The answer is $k=2$. $k=1$ fails by taking $M=\{1,2\}$ and $f_M(\{1\})=\{1,2\}$. Now I show $k=2$ always works. Consider a directed graph $(V,E)$ where $V$ is the set of subsets of $M$ and for every $A$ there is only an edge $A\to f_M(A)$. I claim if $t$ is the smallest integer st $f^t_M(A)=A$ then $t=2^l$ for some integer $l$. This proves that the graph minus self cycles is bipartite, so $k=2$ works. We induct on $|M|$, with the base case, $|M|=1$, clear. Let $x$ be the largest element of $M$. For a set $A$ let $t$ be the smallest integer such that $f_{M \backslash \{x\}}^t(A)=A$. Define $t'$ similarly for $M$. Note for any set $B$, $f_{M}(B)= f_{M\backslash \{x\}}(B) \cup\{x\}$ if $x$ is divisible by an odd number of elements, and $f_{M \backslash \{x\}}(B)$ otherwise. We know $f_M^{t'}(A)=A$ implies $t|t'$. If $t$ works then we are good. Otherwise $f_M^{t'}(A)=A\Delta \{x\}$ where $\Delta$ denotes symmetric difference. So $t'=2t$ Comment on linear algebra. We can interpret elements of $M$ as vectors, and $f_M(A)$ is an additive operation; $f_M(V+W)=f_M(V)+f_M(W)$ in $\mathbb{F}_2^{|M|}$. Therefore if $f_M(V)=f_M(W)$ then $f_M(V\Delta W)=\emptyset$ which implies $V\Delta W=\emptyset$ by noting f preserves lowest element. Thus $f$ is a bijection and the graph of $f$ is a disjoint union of cycles with lengths being integral powers of 2.