You are correct, machen is the most general term and simply means to do something. It does not necessarily imply that one gets the stuff done.
Ich mach mal die Wäsche.
(This usually consists of several steps: Filling the machine, emptying the maching, hanging up the laundry and taking it down again, but when one says that, one is likely only going to do one of those things and leave the machine/the wind to finish the next job.)
It also — much like to do — comes with a plethora of other meanings that I won’t go into here.
Erledigen and ausführen are two rather similar terms. They both imply getting something done (as opposed to just doing something). And in both cases, the imply that the job is not hard (but a robot could execute it, too). Note that computer programs are usually ausgeführt (executed).
Ausführen has the additional connotation of executing an order given by a superior.
Ich erledige noch ein paar Einkäufe.
Der Soldat hat den Befehl des Generals zügig auszuführen!
Leisten and its noun Leistung imply achievement. You have achieved a task and you may be allowed a degree of proudness now. There are other meanings, but again I won’t go into them as they don’t fit in with the other words.
Diese Frau hat in ihrem Leben viel geleistet; sie sollte uns allen ein Vorbild sein!
Finally, vollbringen can probably be translated best with to succeed. A tedious, ugly or otherwise unwelcome task has finally been dealt with and one can now lie down and enjoy the consequences of a done task. Note that miracles (Wunder) will always be vollbracht (if they didn’t simply happen — geschehen).
Es ist vollbracht!
This verb is hardly ever heard in a non-past tense.