Honestly, there may or may not be a direct connection between the overheating and the current problem. Either way, I see no reason to blame it on the shop. The vehicle has 140,000 miles on it.
Because it was overheated, a pressure leakdown test would be a good idea before spending anymore on it. It’s simple and you’d at least know if internal damage has been done prior to investing in persuing whatever the emissions problem is.