Even after editing your question does appears a lot like a request for a tool recommendation. I'll take the approach of recommending a tool type, and leave it to you to decide on your selection criteria.
Estimating costs is done for all sorts of projects, and I have seen estimation tools used for other services. I would be looking for an estimation/price quotation tool. However, it can be done with a spreadsheet (explore the lookup functionality).
I get some info about the number and complexity of project tasks.
This is basically a bill of materials for the project. Ideally your tool will allow to to add notes to each line item and add/change the product later.
I have time-data about past tasks of the same complexity.
This is your product list (tasks that your can estimate somewhat accurately).
I have prices for current tasks.
This is your pricing structure. Depending on the tools, you may have to calculate the costs. If the tool supports assemblies then, your product lists would be assemblies of tasks (hours * rate).
I associate them. (This is a lot of repetitive work.)
This is done once you have done the above.
I apply some a coefficient. (This is a lot of repetitive work.)
Is this your estimation error? I would build this into the product list. If the tool allows for uncertainty about quantity, all the better. If it is a markup/markdown for overhead, than apply the appropriate discount or overhead.
I perform the calculations.
The tools would do this for you.
Hooray, I have an evaluation!