Joe isn't changing anything, although he thinks he is. What's actually happening is that he is somehow able to move between freely between every alternative world in which a Joe exists. The Everett-Wheeler multiple worlds hypothesis is true with a vengeance, and there is an infinity of worlds larger than even God can imagine (literally: Joe says "God does not exist", and is in a world where God doesn't exist).
This explains why he cannot create the mathematically impossible or the physically paradoxical. Worlds such as these have a mathematical probability of zero, so they do not exist and Joe cannot move into one of them.
Presumably there is some sort of Hilbert-hotel permutation of alternative Joes, which is why he never finds himself face to face with himself, and we never notice any paradoxes. (Alternatively, Cantor dust; the infinity of Joe-containing worlds is a smaller infinity than the totality of worlds).
Any mathematicians reading this are advised not to think about it too deeply, because contemplating infinities stacked upon infinities is well-known to be deleterious to one's health. Joe is blissfully ignorant of mathematics beyond his times tables. We might speculate on what his fate might be, if ever "infinity" came to mean more to him than "a very big number".