Make sure the cooler is properly seated and installed.
Check the surface of the APU heatsink (metal stuff on the APU) and the one of the cooler ,make sure they are plane.
Make sure the proper amount of thermal paste is used.Try applying cheap Arctic Ceramique if you are using the cooler factory default now.
The APU should run just fine with an air based TDP 125W compatible cooler ,even with the noisy included one.
The APU takes 75 Celsius ,but you should try and get a maximum 65 Celsius in load.