You have not yet made clear the connection between consistency and your sort of physicalism about mathematics. You've repeatedly brought up issues of completeness and consistency as evidence for your beliefs, but you don't explain why they are evidence for your views.
If formalism is true, then your physicalism is false. If mathematics is just about writing down sets of rules and seeing what conclusions can be drawn, then mathematics is not based upon observations about the physical universe. Sure, we may sometimes write down rules with inspiration drawn from the physical sciences, but that doesn't imply that mathematics in general comes from such a source. For formalists, questions of consistency are superimportant. Consider Hilbert's view that mathematical existence is consistency.
Nothing you've brought up about consistency contradicts anything in formalism. For instance, the formalist is going to want that her axioms for set theory avoid the paradoxes as otherwise her set theory would fail to be consistent. As such, it's not at all clear why your comments about consistency should be taken as evidence for your position. They seem to apply just as well to competing viewpoints.
set theory, being fundamentally based in categorization... the point remains that the axioms are grounded in our everyday experience of categorization and counting.
You assert this, but you don't provide evidence.
In any case, my perfunctory look at this paper indicates to me that it does not support your view.
Perhaps you should actually read the paper before you make claims as to its content. You seem to have a problem with concluding something supports your view when you haven't read it carefully. Consider your reading of the SEP article you linked above:
"Now Gödel was, unlike the later advocates of the so-called Gödelian anti-mechanist argument, sensitive enough to admit that both mechanism and the alternative that there are humanly absolutely unsolvable problems are consistent with his incompleteness theorems. His fundamental reasons for disliking the latter alternative are much more philosophical. Gödel thought in a somewhat Kantian way that human reason would be fatally irrational if it asked questions it could not answer"
How does this demonstrate that Gödel thought the incompleteness theorems were problematic for platonism? This bit you quoted isn't talking about platonism at all.
Obviously, their understanding of physics would be hugely advanced from ours, but moreover certain aspects of physics that we consider to be very difficult to understand would be so commonplace in their experience as to be considered axiomatic. And even the most abstruse aspects of our modern mathematics would be considered as trivial to them as modus ponens.
This is just fanciful imaginings. To see this, let contemporary humans stand in for the aliens in your scenario and Newton-era humans stand in for the humans in your scenario. This is a fair stand in, as contemporary understandings of physics, etc. are hugely advanced compared to that of Newton and his contemporaries. However, aspects of modern physics that would be difficult for a 17th century person to understand aren't considered as self-evident or axiomatic to us. Instead, these advances in science are based upon experiments upon experiments. People study for years to understand modern physics, rather than immediately deducing it as self-evident the moment they walk into a university. Moreover, we don't consider science and mathematics from the 17th century as trivial. One only has to step into a freshman calculus classroom to see that it's not trivial.
My point is that it is naive to believe that we can do mathematics in a vacuum, independent of the limitations of our species and independent of physical basis. The universe is the foundation of what we consider self-evident.
A good rule of thumb is that if you think obvious, undeniable fact X implies your position on a controversial issue, then either X isn't actually obvious and undeniable or else X doesn't imply what you think it does. Academics typically aren't complete idiots. If the obvious fact that we exist as physical beings settled questions about the philosophy of mathematics one way or the other, then we would see an consensus on those questions. Perhaps a few holdouts would deny this clear and immediate argument, but the majority would go along with it. Since there isn't a near universal consensus that mathematics derives from physical observations, you should question your inference here. The alternative is to tar a large number of mathematicians and philosophers are absolute morons.
There's something here I don't understand here. From your very first comment, you've been speaking as though you are well-studied on these issues. Someone who thinks they don't know much about a subject might still have opinions on it, but they won't baldly state their unconsidered opinions as obvious facts. You aren't doing that. You seem to be under the impression that you have some kind of expertise in this subject. Yet this is a question, tagged "mathematics", about the philosophy of mathematics. In the back-and-forth after your initial comment, things have gotten into the particulars of mathematical logic. Your flair reads "Astrophysics | Supermassive Black Holes". That's not mathematics, logic, nor philosophy. Moreover, upon reading your comments, they are riddled with mistakes and misunderstandings.
Why do you think you are in a position to speak authoritatively on the philosophy of mathematics, on mathematical logic, etc.?