That transformer is fine, assuming you're in the US or somewhere with 115V mains. 100VA means it can supply about 4A, which means you can run about 10 solenoids (depending...) at once with no problems. Latching solenoids will save power, but for this project I don't see the point at all due to the additional control complexity (double the number of relays!). While solenoids consume a fair bit of current, they don't actually consume a lot of power: their power-factor is quite low because they're mostly inductive.
An Uno or Duemilanove is plenty powerful enough for this. If you get a 2A 5V switching power supply, that can run your arduino and about 15 relays (depending...) comfortably.
As for the relay board, get one that has 5V (not 24V) relays on it. That one seems to need a 24VDC supply, which is an additional unnecessary complication in your case. Note that I'm talking about the coil voltage, not the contact rating! You still need a mains-rated contact if you want to switch mains devices. Those relays are OK for switching power to solenoids but they're a bit too small/fragile for switching a high power, inductive load like a water pump. You'll need a relay board similar to that one for all the solenoids, plus a powerswitchtail to control the pump.
If you're running out of IO pins, you can of course buy a mega or you can use shift registers to synthesise as many input and output pins as you want - you don't have any stringent timing requirements here (no one will notice if there's 10ms of latency on any switch actions) so you have plenty of time to talk to shift registers or I2C port expanders - look at a PCF8575, MCP23008 or CAT9554 for inspiration; there are many similar parts available.