Let $A$ be a $*$-algebra, $E,$ and $F$ two $A$-modules, and a map $f:E \to F$ such that $$ f(ae) = a^*f(e), ~~~~~~~ a \in A. $$ This seems to me to be the natural generalisation of a conjugate linear map. However, it seems to be too restrictive. Since for, $b$ also in $A$, we must have $$ f(abe)=a^*f(be) = a^*b^*f(e), $$ and $$ f(abe) = (ab)^*f(e) = b^*a^*f(e). $$ Assuming that we have no zero multiplication, this implies that $a^*$ and $b^*$ commute, which means, since $*$ is invertible, that every element of $A$ commutes. Is there something wrong with my reasoning here, or is my definition just too restrictive?

Yes, the problem here is with your definition. It helps to try to keep yourself in the category of modules and module maps, which have to be linear. You don't want to work with conjugate-linear maps.

The basic idea is this: given a complex vector space $V$, define the complex conjugate vector space $\overline{V}$ to be
$$
\overline{V} = \{ \overline{v} \mid v \in V \}
$$
with addition and scalar multiplication given by
$$
\overline{v} + \overline{w} = \overline{v+w}, \quad \lambda \cdot \overline{v} = \overline{\overline{\lambda} v}.
$$
So $\overline{V}$ is the same as $V$ as an abelian group (even as a real vector space) but the scalar multiplication is conjugated.
Then the point is that conjugate-linear maps $V \to W$ correspond to *linear* maps $\overline{V} \to W$.

Now if $A$ is a $\ast$-algebra and $V$ is a left $A$-module, the question is: how do we turn $\overline{V}$ into an $A$-module?
We can't just define $a \cdot \overline{v} = \overline{av}$, because that's not linear in $A$, rather it is conjugate-linear in $A$.
We have the $\ast$-structure, which can fix that problem: we define
$$
a \cdot \overline{v} = \overline{a^\ast v}.
$$
What you wrote in your question amounts to the fact that this is not multiplicative in $a$, i.e. we find that
$$
(a b) \cdot \overline{v} = \overline{b^\ast a^\ast v} = b \cdot (a \cdot \overline{v}).
$$
What this means is that the complex conjugate of a left $A$-module is really a *right* $A$-module, so we really should write the action as
$$
\overline{v} \cdot a = \overline{a^\ast v}.
$$
Similarly, the complex conjugate of a right module is a left module.

So if you want to talk about conjugate-linear maps between modules, really you should have one of them be a left module and one of them a right module.
Say $f : V \to W$ is a conjugate-linear map, where $V$ is a left module and $W$ is a right module.
Then the corresponding *linear* map is
$$
\hat{f} : \overline{V} \to W, \quad \hat{f}(\overline{v}) = f(v).
$$
Now we ask what is the correct compatibility criterion for $f$ in order that the linear map $\hat{f}$ is a map of right $A$-modules.
We want
$$
\hat{f}(\overline{v} \cdot a) = \hat{f}(\overline{v}) a,
$$
which amounts to
$$
f(a^\ast v) = f(v) a, \quad \text{or} \quad f(av) = f(v)a^\ast.
$$