Hi,
The concept is feasable.
Mega would be fine.
The Arduino can read from a K type theromcouple with an interface module.
The output is only 5V, but using an Opto-Coupler and MOSFET to control your relay would do the job.
Opto coupling would help isolate the controller from the heating element switching circuit which would present large switching interference when opening and closing the main contactors.
Keep the controller and K-type circuitry away from the main switching contactors, put then in a separate metal enclosure may be the best bet.
Forget the PWM outputs, they are to to fast for contactor operation.
You would configure your PID for ON/OFF operation over a much longer time period, seconds ,not mS.
Calculating ramp rates is basically some maths, and probably a RTC, Real Time Clock, to keep time, would be best included.
What sort of Visual/HMI are you thinking of?
Interesting project, I many years ago did a similar thing with a laboratory kiln and green bricks ramping up to 1100C in back in 24hours. (Using Ladder Programming)
Tom... 