Yes - if you're using a higher voltage transformer, then you should use higher voltage relays and feed them from before the regulator - but 3VA 1s still too small a transformer.
What would happen if the transformer is too small to power all the relay - would they just not all power on, or would the relay eventually burn out?
No. It means it can put out 12V at up to ~250mA (1/4A). So the tranny is unsuitable and would burn out. You need a lower voltage higher current transformer, e.g. 9V with at least 9VA rating. Bear in mind that the rectified peak voltage is 1.4 times the rated RMS voltage of a transformer, the rectifier drops ~1.4V if it's a bridge type, the rectifier output needs a high value smoothing capacitor, the regulator input voltage needs to be a few volts (depending on regulator type) above its 5V output, and at 750mA the regulator will create a lot of heat so will need a heatsink.
1. According to the stuff I know, your little Transformer will not cut it. It will run very hot while it lasts
2. As per the last question.....the Relays will not burn out eventually as they have never really worked anyway....