I can't give you a jurisdiction specific answer but at common law the situation is as follows.
You had a contract, the basic terms of which were that they promised to do X & Y and you promised to pay them about $1,000. If that is all there is then you are obliged to pay for X & Y and it should cost about $1,000. The fact that they did Z is what is legally known as a "gift" and colloquially as a "f*** up".
However, it is far more likely that you signed a piece of paper with a long list of small-print terms and conditions that you didn't read. One of those probably gives them the right to do work that they reasonably consider necessary and for which you agreed to pay for. In which case you must pay them for the work; this is also called a "f*** up" except its yours not theirs.
In either case, they are not entitled to withhold your car as leverage in the dispute; this is legally called "blackmail". They must take you to court and prove your debt.