Pommie has a good choice for the MOSFET. With a low RDSon, it will dissipate only 1/2W of heat, meaning you may not even need a heatsink. However, if stuck finding that part, the IRL530 will also work, but it has a bit higher resistance (dissipate about 1W at 2.5A), or the IRL520 which will dissipate about 1.75W of heat. With those, I would put on a small heatsink, though it may not be necessary depending on how long you engage the selenoid.
PS: Heed Ron's suggestion, put the fuse at the V+ feed point, not on a ground path....