"This category obviously leads to paradoxes of set theory." What is the paradox?

I interpret the question as not being about the problems of size in category theory in general and how to deal with them (which are fairly well-understood and the subject of other questions on this site), but about what Eilenberg and MacLane actually meant in their original paper. The phrasing of that particular footnote is sloppy, but I think section 6 of their paper ("Foundations") suggests that what they meant is that "this category would lead to paradoxes if we required the objects of a category to form a set rather than something like a proper class".

My guess is that they used the word "aggregate" in the definition in section 2 as a nod to the fact that to be formal, one may want to take these to be proper classes (or something related), but assumed that the average mathematician reading the paper would interpret "aggregate" as "set" at least until they got to section 6. So they added a footnote pointing out that they were aware of the issue, but deferred a fuller discussion of it (and an explanation of what "aggregate" can formally be defined to mean, or other ways one can deal with the problem while still interpreting "aggregate" as "set") to the later section. For instance, in section 6 they wrote "we have chosen to adopt the intuitive standpoint, leaving the reader free to insert whatever type of logical foundation (or absence thereof) he may prefer".

The "paradox" is that, naturally, you also want a 2nd order aggregate at some point. When talking about most functor categories between large categories for example, because a functor $\mathsf{Grp}\to\mathsf{Set}$ in its usual set-like encoding (i.e. the graph of the mapping) is always a proper class, not a set. There are simply too many groups. But at some point you also want to talk about functors between those categories, right? So you need 3rd order aggregates. And so on. And why stop there? Surely you want to put all of them together into a category of all categories! So you need a $\omega$th order aggregate. And then a $(\omega+1)$-th etc.

That's the reason, Grothendieck introduced his universe axiom. In Grothendieck's axiomatisation, there are no classes. All categories are small categories and there is always a bigger set (a universe) which contains whatever collection of things you're looking at right now.

There still isn't a category of all categories though. There are only some categories which contain all strictly smaller categories. Depending on how much you think a proper category of all categories needs to exist, Grothendieck's approach either is an acceptable solution, or a paradox arises in a similar way as it would arise if you wanted a "set of all sets".

Another possible solution is to switch gears entirely and use NF or some other set theory that allows you to form the set of all sets and similar beasts. Again, depending on your viewpoint, this either solves the problem or shifts the paradox somewhere else, because NF (or whatever else you end up using instead) is weird in its own unique ways.