Marco.
As a Brit who did exactly what you are contemplating let me tell you it is not easy.
Okay, I didn't go to Australia just to fly (married an Australian gawd bless 'er) but going to live there fitted in nicely with my career change so that's where I started (again).
At no time did I encounter any difficulty on the basis of not being an Australian (though I took citizenship asap). It's just that by it's very nature the aviation market there is very, very competitive. I reckon I was extremely lucky to get my first job as an instructor on a salary (unheard of!) and then my second job (again salaried) with a regional airline albeit flying piston singles then twins.
To be honest you would see much quicker progress in your career by getting a JAA licence and staying in Europe where you at least have a realistic chance of getting an airline job straight off if that's what you want. An airline/jet job in Australia is never going to happen for a newbie.
That said it was some of the best flying I've ever done and if it weren't for the money (or lack of it) I'd go back.