A little bit late but let me see if I can answer any of these questions for future readers:
1) Yes. The store comes with Paypal Standard and Paypal Express. With the additional Payment Gateway plugin you get Paypal Payments Pro. A list of gateways that come with the plugin can be found here:
2) Not with the default store plugin, but the additional shipping plugin does have an Australia Post module. A list of modules that comes with the plugin can be found here:
3) You can define you own tax zones and tax rates so different states/regions can have different tax rates.
4) The WPOLS plugin works out of the box with most themes. Because of the multitude of available themes and the diverse way in which they are wrote, there are occasional clashes between the them and the store, but there is no comprehensive list of which theme works and which one doesn't. I do not know how the plugin works on a responsive theme, but the CSS for the store has not been designed to be responsive.