DO NOT power from the Arduino, it can only supply a hundred mills or so. You need another power supply, the one you linked to is adequate. You can then use a mosfet or relay module to drive the solenoide. If you use a properly rated avalanche rated MOSFET you will not need the clamp diode.
Good Luck & Have Fun!
Gil