This is not really an answer but an attempt to clear away some of the underbrush and perhaps remove some confusion, so as to formulate the question in a more appropriate context.
As far as I can see, the question is simultaneously about two differences between Eilenberg's treatment of recursiveness and a traditional treatment in terms of (partial) functions whose inputs and outputs are just natural numbers. The first difference is not specific to Eilenberg, but rather is implicit in just about every treatment of traditional recursion theory. Even when one defines recursiveness in terms of functions on the natural numbers (as, for example, in Shoenfield's "Mathematical Logic"), one soon applies the notion to any sort of finite objects as inputs and outputs, for example, finite strings over a finite alphabet, or hereditarily finite sets. This change of context is usually accomplished by Gödel numbering, but there are also places where one or another of these alternative contexts is taken as the basic one. If I remember correctly, Shoenfield wrote a small book on recursion theory in which he took functions on strings as primitive, and Barwise's "Admissible Sets and Structures" undoubtedly takes functions on hereditarily finite sets as basic. These variations are essentially ignored in most situations because it is so routine to translate between them.
Now starting with a version of recursion theory based on strings, one can describe the step to Eilenberg's approach as shifting to a much more algebraic point of view. Of course, the set of strings on a finite alphabet is the free monoid on that alphabet, the monoid operation being concatenation. Eilenberg essentially develops the basics of recursion theory as a branch of monoid theory. I don't have his book handy, so I can't say how much he generalizes from free monoids to general monoids. [I disagree with the notion in one of the comments that Eilenberg's contribution is a generalization from the commutative monoid of natural numbers to non-commutative monoids; strings over non-singleton alphabets (and thus non-commutative free monoids) were in recursion-theoretic use for as long as there has been recursion theory --- maybe even longer, depending on how you view Post's production systems from the 1920's.]
I think I've finally arrived where I can ask a clear form of the original question: What benefits do we get from Eilenberg's algebraization of recursiveness in terms of monoids? Some people would consider it an advantage just to be able to say we're doing algebra rather than logic; needless to say, as a logician, I don't consider that a real advantage.
