Choosing the right MOSFET for 5V power relays
Since relays are a lot slower than any MOSFET, your only concern are the DC parameters.

The MOSFET must be able to handle a \$V_{GS}\$ > 5 V

The MOSFET must be able to handle a \$I_D\$ > 250 mA

You also need to be sure that the MOSFET switches on properly when you apply \$V_{GS}\$ = 5 V.

When the MOSFET is switched on it needs to have a low enough resistance \$R_{DS,on}\$ so that it will not drop much voltage. At only 250 mA a value of less than 0.5 ohm should be OK. Many MOSFETs will have a much lower \$R_{DS,on}\$.

It is also OK to use a hugely overspecified MOSFET. For example, if you have some MOSFETs lying around that are large and can handle 20 A but their size isn't an issue, you could use them, I mean, that would work fine.

The two MOSFETs you found look quite expensive to me. To keep things cheap (and for hobby projects, not professional use) I look on Ebay and find the cheapest MOSFETs which can do the job. A very common and cheap type is the AO3400 which costs around 10 Euro cents (including shipping) if you buy 20 from China.