Can I buy an HP all in one #5610,and fax with it, with fios?

Traditionally VOIP systems have problems with modems. It depends on the baud rate. I don't know how FIOS behaves, but usually 9600 baud, which is the general standard for fax machines is OK.

Try faxing with windows FAX driver. If you don't have problems, then I'd say your safe.