I can't find a reference now, but apparently the first "self-service" store in Australia was the original Coles Variety Store in Smith St, Melbourne, opened in 1914.

[1] http://collections.museumvictoria.com.au/articles/1901

Today, Coles is one of the big two supermarket "duopoly" and "self-service" refers to those robotic checkouts that are actually slower and more infuriating than being assisted at the counter to ring-up your purchase. Interestingly, the structure of checkouts now suggests that less shoppers use trolleys than I seem to recall from a few decades ago.

Another piece of trivia: I don't think I've ever seen a plastic trolley in Australia.