Mario and Luigi (as well as most other humans in the Mario universe) are from Diamond City, which is far from the Mushroom Kingdom
In the RPG Mario games, the cities are often populated by a single species, with the occasional outsider. (e.g. Toads in Toad Town, Goombas and Koopas in their respective villages.) Diamond City is where humans come from, as most characters from Mario games aren't really mentioned in WarioWare outside of microgames. Also, pretty much everyone in Diamond City is weird in some way, this would include Mario and Luigi's superhuman abilities and large noses.