Editar el HTML de la barra de navegación en WordPress

Sí, necesitarás implementar la clase walker para esto.

Aquí tienes un ejemplo sencillo.

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

wp_nav_menu( $defaults );

En el bloque de código anterior, la función wp_nav_menu() toma $defaults como argumento. En el array $defaults, la última clave es walker. El valor de la clave walker es un objeto de la clase Primary_Walker_Nav_Menu.

En el archivo functions.php implementa el siguiente código:

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";
    }
}

El método start_el() se utiliza para agregar la etiqueta HTML de apertura para un solo elemento del árbol (como <li>, <span>, o <a>) a $output.

El método start_lvl() se ejecuta cuando el walker alcanza el inicio de una nueva "rama" en la estructura del árbol.

Generalmente, este método se usa para agregar la etiqueta de apertura de un elemento HTML contenedor (como <ol>, <ul>, o <div>) a $output.

El resultado de la implementación anterior generará el siguiente 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">Servicios</a>
      <ul class="dropdown-menu" role="menu">
         <li><a href="http://karunshakya.com.np/services/selection-et-recrutement/">Selección y reclutamiento</a></li>
         <li><a href="http://karunshakya.com.np/services/mise-disposition-de-personnel/">Puesta a disposición de personal</a></li>
         <li><a href="http://karunshakya.com.np/services/gestion-de-salaire/">Gestión de nómina</a></li>
      </ul>
   </li>
   <li><a href="http://karunshakya.com.np/news/">Noticias</a></li>
   <li><a href="http://karunshakya.com.np/medias/">Medios</a></li>
   <li class="last-child"><a href="http://karunshakya.com.np/contactez-nous/">Contáctenos</a></li>
</ul>

Cómo usar la clase Walker:
http://code.tutsplus.com/tutorials/understanding-the-walker-class--wp-25401

Si solo deseas cambiar los elementos externos (no los li en sí mismos), puedes pasar a wp_nav_menu() el argumento 'items_wrap' => '<ul id="%1$s" class="%2$s">%3$s</ul>' y editarlo según sea necesario. Por ejemplo, esto muestra cómo envolver la lista en un elemento nav y un elemento div:

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

También puedes pasar otros elementos para editar el contenido del <li> y del <a> usando 'before' => '', 'after' => '', 'link_before' => '', 'link_after' => ''.

Si eso no ayuda, por favor muestra el resultado HTML final que estás intentando obtener.