.ms-core-listMenu-verticalBox UL.root > LI > .menu-item {
 /*Style each menu item*/}  .ms-core-listMenu-verticalBox > ul.root > li.static > ul.static > li.static > a:hover {
 /*Style on hove sub items*/}  .ms-core-listMenu-verticalBox > ul.root > li.selected > a {
 /*Style selected top level item*/}  .ms-core-listMenu-verticalBox > ul.root > li > a:hover {
 /*Style top level mouse hover*/}  .ms-core-listMenu-verticalBox > ul.root > li.static > ul.static > li > a {
 /*Style sub level mouse hove*/}  .ms-core-listMenu-verticalBox > ul.root > li.static > ul.static > li > a.selected {
 /*Style selected sub item*/}  .ms-core-listMenu-verticalBox a.selected {
 /*Style Selected Item*/}  .ms-core-listMenu-verticalBox UL.root UL {
 /*Style Outer Box*/}

function AppendMenuFontAwesomeIcons() {
    var elements = document.querySelectorAll('ul[id^=zz][id$=_RootAspMenu] li span.menu-item-text');

    for (var i = 0; i < elements.length; i++) {
        // Here you can make a switch case statement or something to define the displayed icon
        elements[i].innerHTML = '<i class="fa fa-fw fa-star"></i> ' + elements[i].innerHTML;
    }
 }

_spBodyOnLoadFunctionNames.push('AppendMenuFontAwesomeIcons');