What is a suitable temperature rise for PCB traces?
The number you need is called "MOT" (maximum operating temperature) for the laminate you have in mind. You also need to know what the internal temperature will be in your product (including the heat the relay connections add). For FR-4 to maintain electrical properties, that might be 130°C (a bit higher for mechanical properties). If the maximum temperature in the vicinity of your PCB will not exceed 60°C you could conceivably allow for 70°C rise. For FR-2 it might be 105°C, so the limit might be 35°C rise.  

More normal practice is to allow for 20-30°C to keep the PCB from getting all discolored and weak over time and there might be issues with component life if you add too much heat. It's conceivable UL approvals might be complicated with internal temperatures exceeding 105°C. 

There are some very nice higher temperature laminates with Tg = 170°C available, and commensurately higher MOT, but it's cheaper to use 2oz copper. 

Other options are to pull back the solder mask and parallel the conductors with solder (assuming wave soldering), or to solder a jumper wire in place of, or in parallel to, the conductor. If you can keep the conductors short in length, most of the heat will get sunk out of the pins. Look at the design of any PC power supply for ideas, just about every penny has been pinched in their design.