The following operators have both Cairns and Horn Island bases and pay at or above the award.
1. Regional Pacific Airlines, DHC6 x 2 (RPT/Chtr)
2. Barrier Aviation, BN2 x 3 C207 x 1 C402B C402C (Chtr only)
3. Skytrans, BN2, C310 (RSTOL equipped) C404 (RPT/Chtr)
4. Coastwatch / Surveillance Australia / NJS, BN2, (non commercial)
There are other operators there as well, but they DO NOT pay or comply with the award.
If the one you're thinking of is not listed, suggest you contact 1 - 4 above instead.
Horn Island is an expensive place to live but offers some of the best flying you'll get in your GA career.
It is initially challenging, the scenery is fantastic and Torres Straits Islanders are great passengers and people.
Cairns is a great place to live, probably the best place you'll ever work in GA.
You'll be working out of Australia's 4th or 5th busiest airport, and it's an international port at that.
Plenty of ILS's to prepare you for the next step, plenty of terrain to scare you, satisfying, professional flying guaranteed.
It has all the conveniences of a modern city, even a Myer store,
accommodation ranges from moderate to expensive, but way ahead of Darwin with what you get for your dollar.
If you haven't applied to Skytrans (staffcv.com only) then do so, arguably one of the best GA operators in Australia,
they pay well, they're nice people, they maintain their aircraft properly, definitely should be your 1st choice.
Hope you're not considering one of the "boy-burners" instead.
Yes, you need 500 multi and 1,500 total as expected minimums,
and reasonable IF time (there is no such thing as "planned IF time" in the regs, flight under the IFR is IF flight.)