It's common to get the "heater over powered" warning with E3D hot ends since they started including silicone socks with them.
The expected rate of temperature increase depends on the actual temperature. What I suspect is that you're print cooling fan is cooling the heater block too much. Try to direct the print cooling fan air at the print, not at the heater block. If all sales fails you can do the heater tuning with the print cooling fan turned on, but then you will probably get some temperature overshoot during initial heating.