I believe the plugin you were using only has Font Awesome icons, correct?
Using the Menu Icons plugin, go to “Appearance > Menus” and you’ll see Menu Icon Settings on the left. In there you can choose to display Font Awesome icons, as well as some other icon libraries.