It is supremely difficult to get the French, Dutch, or Portuguese to colonise Australia in the 18th century; they've simply no reason to do so. Britain colonised the place only as a means to get rid of prisoners. Australia really doesn't have much going for it for an 18th century European - arid, far away, no obvious resources and no plunder. The best way, I think, is to butterfly the British need to for a penal colony away and push colonisation up to the 19th century. Even then though there's the problem of New Zealand, which was colonised under very different circumstances to Australia, and which would encourage the British to claim Eastern Australia by virtue of security, and that Australia remains far away and seemingly resource poor. You need to find a reason for other European states (or maybe non-European if you're particularly adventurous) to want Australia. Non-British western Europeans never seemed quite so keen on settler colonies, or had quite the culture of penal deportations. To feasibly get other Europeans to come here you probably need an early POD or some rather specific circumstances in the 18th/19th centuries. Certainly possible, but not at all simple.
As to having two or more states in Australia, this is quite possible but only if the colonisation is simultaneous, or part of the continent is gained through war. 3/4ths of the population is concentrated in the South-Eastern quarter (including Brisbane), and for good reason. It's where all the good stuff (by 18th-19th century standards) is located. To get two states, this area basically needs to be shared, unless you want one to totally dominate the other. Probably the easiest and most stable way of doing this is to have one state based in OTL Victoria and the other east of the dividing range, with the rest of the continent shared somehow, or maybe with the resources of the south east diluted occupied by a third party. This still leaves the Murray-Darling system as a point of serious contention, but that's probably more interesting. It's also important to remember that all these states would have very small populations, with strong potential for economic issues.