Possibly the way to go then is first get your name change, that allows you to change your driving licence, medicare card, passport, and police checks for working with vulnerable people. The birth certificate is pretty well irrelevant for all of that (I've never shown mine to anyone!).
You can change your name whenever you wish, just google name change in SA and it tells you how.
For the others to change your gender marker you need a letter from Dr Lyons saying that you are undergoing a medically supervised transition to your affirmed female gender and for your documents to be changed appropriately. It is a form letter that everyone gets on request with just the names are changed about who it concerns.
The two good ones to change is the driving licence and passport as they then become your official ID for everything else.
Hopefully that should clear up any work issues.