How do you identify one capable to teach CS, capable to teach ages K-12, and willing to work for very little pay? Is the goal to train existing teachers (would they make more money because of it?), or hire a CS veteran to teach?
This gets complicated because of teacher's unions, but I think it's the best bet at getting high quality folks in CS classrooms.
Others will mention HS math teachers. Having spent enough time in US k12 classrooms to have an opinion on this topic, I think this can work out really well, but I'm not at all convinced it's a panacea. Mostly because many, many HS math teachers have learned how to teach specific math courses, but don't actually have a firm understanding of mathematical thinking in general. Training them to become CS teachers will fare about as well as teaching history teachers to become CS teachers (again, it can be great but lots of variance).
Your proposition also assumes that you have enough Maths teachers, which Australia is certainly lacking (for the same reasons as OP)
I doubt they intend on teaching much beyond the basics at that level, which shouldn't be hard for any teacher to learn.
That's mathematics, not didactics of mathematics.