How to tell if this MOSFET work with this Solenoid

I am trying to figure out if this solenoid:

will work this MOSFET:

using a 5v signal from an Arduino.

I am guessing it will because:
It is marked as a Logic Level MOSFET
The gate threshold level is 1.6 which well below 5 volt from the logic pin of the Arduino (Is it too low? will 5 volts from the arduino fry it?)
the mosfet is rated for 10 amp continuous and the solenoid only needs 350mA
the mosfet is rated for 100 volt and the solenoid only needs 12

Am I right that this mosfet will be able to fully drive the solenoid using an output pin from the arduino? If so, is it way overkill? Is there a cheaper mosfet that will work equally well?

Yes you seem to have all the basis covered, it looks fine.
It is not massive overkill and in fact is quite a modest FET by modern standards. You can get them with much lower on resistance, but it is fine for what you want.