It's part of what's called the Universal Service Obligation (USO) for which Telstra (the dominant carrier) is responsible for delivering:

https://www.infrastructure.gov.au/media-technology-communica...

The money comes from a levy on telecommunications carriers (Telstra included, but also most of it's competitors). There was a bit of conjecture in the media that the "free" payphones were really being paid for by the other telcos, once the money Telstra contributes is discounted.