When Vin goes below your minimum Vin you are going to have your output drop. I have seen many times that people think it will be a small drop and it ends up dropping very quickly when the Vin goes to low.
If you want something that give you 5 out from 4.5 to 18V in, then you should just pick a simple Buck-Boost DC-DC converter. They will be able to handle from 2V to higher than 18 without a problem. By grace of being a buck boost, they can step your voltage either direction and it should make your life quite easy.
Use full wave rectification, not half wave. HW uses transformer poorly, may not be good or TEC, has no obvious advantages except the cost of 3 diodes.
If you want to operate it at full power with no control of cooling level then 12V is fine. LM350 regulator needs about 3V headroom. So 12V out from regulator = 15VDC in min.
Full wave rectified transformer will give ABOUT Vmax DC ~= 1.4 x AC voltage.
Or VAC_min ~= (Vdc + dropout) / 1.4
So 12V + 3V = 15V
VACmin ~~~~= (12 + 3) / 1.4 =~ 11 VAC if ~= NO ripple voltage
ie 12 VAC transformer will give 12 VDC after regulator if well smoothed.
More is better, so maybe 14 VAC - 15VAC will allow regulator headroom plus some ripple allowance.
If all you want is to run it at full power then a transformer, bridge rectifier, smoothing capacitor and series resistor are all that is needed. Resistor drops excess voltage. A 10 VAC transformer will be about enough (1-VAC x 1.4 = 14 V with smoothing and ripple) and 12 VAC will definitely be enough. Resistor dissipates 2.5 Watts per volt of drop. A length of Nichrome wire adjusted to provide correct voltage to Peltier is one option or 0.4 Ohms per volt of drop select-on-test.
Regulator WILL need heat sink - how much depends on transformer. At say 3V regulator drop - about the minimum you should figure on, the dissipation V x I = 3V x 2.5A = 7.5W. Say allow 10 Watts. More if transformer is of excessive Voltage.
Heatsink can be selected using degree C (or K) per Watt for commercial heatsinks. For a 10C rise at 10 Watts you need 1 C/W heatsink which is "very large indeed".
If you want heatsink at almost cool enough to touch (almost) say 60 C the if ambient = 30 C worst case heasting delta T = 60-30 = 30C so heatsink = 30C/10W = 3 C/W
Even that is largish. Going other way, 10C/W is common so 10 W = 10W x 10 C/w rise = 100C./ Add ambient + Tsink = 100C rise + 30C = 130 C.
You rally don't want 130 C heatsinks.
so somewhere between 3 C/w and 10 C/W leaning towards 3 C/W end.
Fans and Peltier together are OK. Fan load is small compared to Peltier load.
Fans could run from smoothed DC before regulator - maybe with a dropping resistor of their own suited to VFan an Vdc.
Strip board construction OK but keep wires short and heavy. If running higher currents along a piece of stripboard you can solder wire to the strip for longer high current leads or use a wire link from points to be joined.
Main mains caution is DON'T PLAY WITH MAINS whn not needed. eg here all the circuitry is LV apart from mains feed to transformer primary. Do the primary side wiring well. Insulate as required. Then leave it alone.
Best Answer
What is REALLY important is to have 0.01-1uF ceramic capacitor soldered right on the power pins of every digital IC in your circuit no matter what is the power source.
So I belive even your current PSU will be fine if you add ceramic caps where needed. Linear regulators provide very stable power, so you should be good with what you have now (unless it is oscilating - might happen if ESR of caps does not match regulator requirements - usually happens on LDO regulators rarely).
In my projects I use USB as my main power source. It gives you stable 5v and it does have current limiter.
You can ether get it from your PC(should be careful a little) or from tiny mains adaptors which have USB output.
Then you use your linear regulator if you need less then 5V.