A fluid leak from a pressurized system in my mind would not warrant the need to flush the system. Since the transmission fluid would be under pressure, there shouldn't be much opportunity for contaminants to get in to the fluid system. The possible caveat to this would be if the system used suction to pull the fluid through rather than pressure to pump the fluid.

The labor rate to change the heat exchanger should include the evacuation of the AC system and to put it back to the same condition as when it was brought in. The shop should be able to determine how much R-134a they recovered but there may be an extra charge for a bit of R-134a during the recharge process due to normal loss over time and through opening the system, assuming the system was working properly when you brought the vehicle in.

-Rod