That's a challenge. I was once involved in the pre-study of a project in Peru. It turned out to be high up in the Andes - about 4000 metres above sea level. One of the problems was that we needed to derate equipment due to thin air and reduced cooling. But a paper mill is more likely to be at sea level. So that shouldn't be a problem. But keep an eye open for cooling problems if you are moving up the mountainside.
Running the 380 V motors on 460 V 60 Hz is just fine. But there is a risk that the 20 percent increase in speed will cause overload in pumps and fans.
The 500 V motors will not be happy at all with 460 V 60 Hz. They will be running at close to 25 percent undervoltage and that is not good. You will have a large slip and lots of rotor heat. A 500V/50Hz motor expects 600 V at 60 Hz.
Rewinding or not all depends on how many 500 V motors you have and how big they are. There is a reason for the 500 V - perhaps large units, perhaps because you usually run such systems with an isolated neutral. That underlying reason may also influence your choice of action. Is keeping the two systems separate totally unrealistic?
Contactor coils. If you feed the control transformers with 460 V 60 Hz, your AC coils will probably be happy with their new voltage/frequency combination. But you will have to be careful with your DC coils. They will have almost 50 percent more heat. And that may be a problem. A big problem, really.
You will also have to check other DC-fed things like proximity switches and such little devices. They usually have a maximum voltage equal to 30 V DC and since they already (in Europe) see about 27 V, you will be on the margin with a 20 percent higher voltage (1.2x27 = 32 - 33 V).
And there are the VSDs. They may be frequency inverters or DC drives. You will need to make sure they can operate with the voltage available.
Plus a few other things that you will find out on place - sometimes before, sometimes after something lets the smoke out.
Gunnar Englund