The most obvious answer is that being a coach in Queensland, the heart of Australian swimming, is an upgrade over squeezing as much out of a country with slightly less population than the state of Massachusetts. The compensation is probably better, and the swimming atmosphere far more rabid.
It's also possible that coaching in Denmark had started to wear on Paulus. As I mentioned when I wrote about him earlier this year, Paulus was always bluntly critical in a way that would get him quickly out of a job in the US. This fall, that resulted in public statements that were harshly critical of Danish club coaches, who fired back with their own series of volleys, ending with a coach who was just a few towns away from Paulus' National Training Center calling for his resignation.
The difference between coaching in Denmark and many other rabid sporting nations is that it's really not possible to be the "hero coach" in Denmark. In the US, I often notice that the best coaches get a mythology weaved around them as they rise the ranks, one which only gets occasionally tarnished by anonymous internet commenters. You would be hard pressed to find someone consistently and publicly criticizing the biggest coaches in the US.
Denmark is different. Again, Paulus was the most successful coach in Danish modern history, yet he had no shortage of detractors. That's a good thing for the Danes culturally but will also present a challenge for them as they seek to recruit another coach to fill Paulus' position. Denmark has now changed coaches after each of the last two Olympic games, a cycle they hoped to avoid this time around but unfortunately couldn't. Now, a whole new set of leaders atop Danish swimming must set the way forward, and fast.