Modificare l'HTML della barra di navigazione di WordPress

Sì, dovrai implementare la classe walker per questo.

Ecco un semplice esempio.

$defaults = array(
    'theme_location' => 'primary',
    'container'      => 'ul',
    'menu_class'     => 'nav navbar-nav main-nav',
    'walker'         => new Primary_Walker_Nav_Menu()
);

wp_nav_menu( $defaults );

Nel blocco di codice sopra, la funzione wp_nav_menu() prende $defaults come argomento. Nell'array $defaults, l'ultima chiave è walker. Il valore della chiave walker è un oggetto della classe Primary_Walker_Nav_Menu.

Nel file functions.php implementa il seguente codice:

class Primary_Walker_Nav_Menu extends Walker_Nav_Menu {
    function start_el(&$output, $item, $depth = 0, $args = array(), $id = 0) {
        if (array_search('menu-item-has-children', $item->classes)) {
            $output .= sprintf("\n<li class='dropdown %s'><a href='%s' class=\"dropdown-toggle\" data-toggle=\"dropdown\" >%s</a>\n", ( array_search('current-menu-item', $item->classes) || array_search('current-page-parent', $item->classes) ) ? 'active' : '', $item->url, $item->title
            );
        } else {
            $output .= sprintf("\n<li %s><a href='%s'>%s</a>\n", ( array_search('current-menu-item', $item->classes) ) ? ' class="active"' : '', $item->url, $item->title
            );
        }
    }

    function start_lvl(&$output, $depth) {
        $indent = str_repeat("\t", $depth);
        $output .= "\n$indent<ul class=\"dropdown-menu\" role=\"menu\">\n";
    }
}

Il metodo start_el() viene utilizzato per aggiungere il tag HTML di apertura per un singolo elemento dell'albero (come <li>, <span>, o <a>) a $output.

Il metodo start_lvl() viene eseguito quando il walker raggiunge l'inizio di un nuovo "ramo" nella struttura ad albero.

Generalmente, questo metodo viene utilizzato per aggiungere il tag di apertura di un elemento HTML contenitore (come <ol>, <ul>, o <div>) a $output.

L'output dell'implementazione sopra riportata risulterà nel seguente HTML:

<ul id="menu-main-navigation" class="nav navbar-nav main-nav">
   <li class="dropdown ">
      <a href="http://karunshakya.com.np/services/" class="dropdown-toggle">Servizi</a>
      <ul class="dropdown-menu" role="menu">
         <li><a href="http://karunshakya.com.np/services/selection-et-recrutement/">Selezione e reclutamento</a></li>
         <li><a href="http://karunshakya.com.np/services/mise-disposition-de-personnel/">Messa a disposizione di personale</a></li>
         <li><a href="http://karunshakya.com.np/services/gestion-de-salaire/">Gestione degli stipendi</a></li>
      </ul>
   </li>
   <li><a href="http://karunshakya.com.np/news/">News</a></li>
   <li><a href="http://karunshakya.com.np/medias/">Media</a></li>
   <li class="last-child"><a href="http://karunshakya.com.np/contactez-nous/">Contattaci</a></li>
</ul>

Come utilizzare la classe Walker:
http://code.tutsplus.com/tutorials/understanding-the-walker-class--wp-25401

Se stai cercando di modificare solo gli elementi esterni (non gli stessi li) puoi passare a wp_nav_menu() l'argomento 'items_wrap' => '<ul id="%1$s" class="%2$s">%3$s</ul>' e modificarlo come necessario, ad esempio questo mostra come avvolgere la lista in un elemento nav e un elemento div:

'items_wrap' => '<div><nav><ul id="%1$s" class="%2$s">%3$s</ul></nav></div>',.

Puoi anche passare altri elementi per modificare il contenuto del <li> e del <a> usando 'before' => '', 'after' => '', 'link_before' => '', 'link_after' => ''.

Se questo non ti aiuta, per favore mostra l'output HTML finale che stai cercando di ottenere.