You can pay the customs fees and local taxes yourself if you're shipping with Fedex/UPS, it's just a checkbox if you have an actual account with them.

Also you can certainly ship batteries via UPU network (Australian Post) but there are strict packaging rules you need to follow[1].

You don't really go into any detail as to why they didn't accept your package. Did you attach properly filled out CN23 label?

[1] https://auspost.com.au/content/dam/auspost_corp/media/docume...