AU consoles are the same as EU and should have EU eShop, since AU falls under Europe for historical reasons, your eShop is EU, but it could be that the game is already released in some EU countries, or whole Europe exluding AU
Possible yes, but you'll have to unlink your NNID and make a new EUR one to do it. Before NNID was introduced to the 3DS it was possible to just change the region in the system settings but if you do that with a NNID linked you'll be unable to use the eShop until you change back.