Category of multisets
This is typically a situation in which there no most natural way to do things. As long as your definition is indeed a category, it will be as good as mine, depending on the application in mind. (In that sense it is really not a good exercise from Aluffi, because it becomes a problem of set theory/combinatorics and not of category theory.)
(1) You could draw inspiration from the "standard multisets", where the most obvious way to define a morphism is as a morphism of the category $\mathsf{Set}/\mathbb N$, meaning a function that preserves multiplicity. Then of course multiplicity is quite more intricate in the case of "sets with an equivalence relation" where you need to count with cardinals instead of numbers: preserving multiplicity becomes preserving cardinality, and you can define a morphism as $f: A/{\sim_A} \to B/{\sim_B}$ such that for any $a\in A$, the set $[a]_{\sim_A}$ has the same cardinality as $f([a]_{\sim_A})$, meaning there is a bijection between them (just not naming which one).
(2) Now you could say that in the case of standard multisets, the number $m(a)$ for $a\in A$ is not so much about counting the appearance of $a$ than it is about having $m(a)$ names to refer to the object $a$ (namely $a_1,\ldots,a_{m(a)}$) and then a map between multisets owes to keep track of these names: a map $f: (A,m) \to (B,n)$ should not only map an element $a$ to an element $b$ with as many names, but also describe how to rename $a_i$ in one of the $b_j$. In that setting, a map of standard multisets $(A,m)\to (B,n)$ has to be defined as a map $f: A\to B$ together with permutations $\sigma_a \in \mathfrak S_{m(a)}$ for each $a\in A$. Mimicking this process in the infinite case, the "names" of $[a]_{\sim_A}$ are precisely the elements of $A$ that are in the class of $a$, and the maps based on the above interpretation are then maps $f: A/{\sim_A} \to B/{\sim_B}$ together with given bijections $\phi_k : k \to f(k)$ for each of the classes $k\in A/{\sim_A}$. Remark that these maps are equivalently these equivariant $f:A \to B$ (meaning $a\sim a' \implies f(a)\sim f(a')$) such that the restrictions $f\mid_{[a]}: [a]_{\sim_A} \to [f(a)]_{\sim_B}$ are bijections.
(3) You could now do one jump further and consider that it is acceptable to map a element $a$ with $m(a)$ names to an element $b$ with $n(b)$ names even if $m(a)\neq n(b)$ as long as you continue to keep track of to which of the $b_j$ is mapped each $a_i$. Then in the finite case maps $(A,m)\to(B,n)$ are just maps $f: A\to B$ together with maps $\phi_a: \{1,\ldots,m(a)\} \to \{1,\ldots,n(f(a))\}$. In the infinite case, it then should be defined as a map $f: A/{\sim_A} \to B/{\sim_B}$ together with maps $\phi_k : k \to f(k)$, or equivalently as equivariant maps $A\to B$ (and this is back your first try, but it seems much less worrying with that name-interpretation in mind).
Remark that all these are instances of the same process: they are (equivalent to) the Grothendieck construction of pseudofunctors of the form $\mathsf{Set}\ni A\mapsto \mathbf C^A$ for a category $\mathbf C$ whose objects are (finite) sets.
- (finite) sets and a unique map $A\to B$ whenever $A$ has same cardinality than $B$,
- (finite) sets and bijections
- (finite) sets and functions
You can try other such $\mathbf C$ to find other definitions of a multiset category. As long as there is a unique map from the singleton to itself in $\mathbf C$, you should be able to embed $\mathbf{Set}$ as a full subcategory in the resulting Grothendieck construction.
And this is probably not the only way to construct a solution to the exercise (I have a small voice in my head saying "Bishop's setoids" but I know to little about that to see if it gives something acceptable here.)