Use any markup in Genesis example. Starting with the Genesis Sample. This example code goes in your child theme's functions.php file. NOTICE: that the id on the nav is #foo-nav if you use skip links (and you should) you will need to filter the genesis_skip_links_output.

any-markup-in-genesis.php

<?php
// don't include this

/** ====================================================================================
 * 
 * Use any markup in Genesis example. Starting with the Genesis Sample. 
 * This example code goes in your child theme's 
 * functions.php file. NOTICE: that the id on the nav is #foo-nav 
 * if you use skip links (and you should) you will need to filter 
 * the genesis_skip_links_output.
 * 
 * Also, using CSS to match and NOT doing this would be a better idea IMO
 * 
==================================================================================== **/


/** ====================================================================================

 * remove exisiting Genesis Markup for new foo_header

==================================================================================== **/

remove_action( 'genesis_after_header', 'genesis_do_nav' );
remove_action( 'genesis_header', 'genesis_header_markup_open', 5 );
remove_action( 'genesis_header', 'genesis_do_header' );
remove_action( 'genesis_header', 'genesis_header_markup_close', 15 ) ;
unregister_sidebar( 'header-right' );


/** ====================================================================================

 * New header markup

==================================================================================== **/

function foo_header () {

    $header_classes = 'c-layout-header c-layout-header-4 c-layout-header-default-mobile';
    
    $header_wrapper_classes = 'c-topbar c-topbar-light c-solid-bg';
    
    $nav_reg = 'foo-menu'; // or 'primary' for genesis

    $nav_func = 'foo_do_nav'; // or 'genesis_do_nav' 
    
    // OR register a sidebar to use a widget instead of wp_nav_menu if you use menu plugin that uses widgets.

    // header markup
    echo '<header class="'.$header_classes.'" data-minimize-offset="80" itemscope itemtype="http://schema.org/WPHeader">';
    echo '<div class="'.$header_wrapper_classes.'">';
    echo '<div class="container">';
    echo '<!-- BEGIN: INLINE NAV -->';

      if ( has_nav_menu( $nav_reg  ) ) {
    
          do_action($nav_func); 
        
     } 
    
    echo '</div><!--/.'.$header_classes.' -->';
    echo '</div><!--/.container -->';
    echo '</header><!--/.header '.$header_classes.'-->';

}


//* add the 'foo_header' into the genesis location 'genesis_before_header'
add_action( 'genesis_before_header', 'foo_header' ) ;


//* add the the 'foo_custom_menu' to the 'foo_do_nav';
add_action( 'foo_do_nav', 'foo_custom_menu' );



/** ====================================================================================

 * Register a new menu
 * https://codex.wordpress.org/Function_Reference/register_nav_menus

==================================================================================== **/

function foo_register_new_menu() {
  
  register_nav_menu( 'foo-menu', __( 'Foo Menu', 'your-text-domain') ); //your theme's text-domain for localization, google for learning this.

}
add_action( 'after_setup_theme', 'foo_register_new_menu' );



/** ====================================================================================

 * Create the registered 'foo-menu'
 * wp_nav_menu
 * https://codex.wordpress.org/Function_Reference/wp_nav_menu

==================================================================================== **/

function foo_custom_menu() {

    $items_wrap = '<h2 class="screen-reader-text">Primary Navigation</h2><nav class="c-top-menu c-pull-left" id="foo-nav" itemscope="itemscope" itemtype="http://schema.org/SiteNavigationElement"><ul id="%1$s" class="%2$s">%3$s</ul></nav>';

 	$args = array( 
	'theme_location'  => 'foo-menu',
	'menu_class'      => 'my-menu-class', // on ul
	'echo'            => true,
	'link_before'     => '<span>',
	'link_after'      => '</span>',
	'items_wrap'      => $items_wrap,
	'depth'           => 0,
	'walker'          => ''
   ); 
   wp_nav_menu( $args );
   
}

Also will need to localize the screen reader text on the $items_wrap.