Overall it sounds doable.
One thing you have to worry about: how representative is the temperature right under the heating element for the bulk temperature of your object? That's one thing that I saw in your description as a potential issue. The heating element itself tends to be at a (much) higher temperature than the bulk of the material.
Where do the solenoids come in? Those are coming a bit out of the blue. You're talking about heating elements to heat up an object, and then there are these relay operated solenoids. What's the function of those?
So you have the PID control of a single heating element done, that's great. To keep them in sync, I would use a single setpoint/target temperature that is communicated to all these controllers. Change that setpoint over time to force the heating elements to follow, but at a speed that they can all follow fast enough. So for your 150 deg/hour change that could be a 0.1 deg increase every 2.4 seconds. For your first heating up you could make that faster of course.
It'd be easiest if you can fit all on one Arduino (a Mega has 15 PWM outputs - otherwise you may consider an external PWM pin extender).
Key to this approach is the setpoint: when at room temperature you don't immediately make it 100 C, asking the heaters to heat up as fast as they can, but you increase it at a speed the slowest heater can follow. The PID controls themselves should do the rest: speeding up the slow ones, slowing down the fast ones.