Eyeballing Macca's Australian website [1], I'd say that the furthest point would be equidistant from Kalgoorlie, Broome and Alice Springs. That's pretty close to the north-eastern corner of the Gibson Desert Nature Reserve [2], 800km from the nearest McDonalds.

[1] http://mcdonalds.com.au/find-us/restaurant

[2] http://g.co/maps/pehrm

Yeah, somewhere between Swan Hill, Mildura and Horsham. Big Desert, or into eastern SA would get you a fair way from a McDonalds.