Editing or filtering the output of the Genesis navigation

You could try to use the wp_nav_menu_args filter (untested):

/**
 * Add the Menu_With_Data_Attr walker to the wp_nav_menu() used by genesis_do_nav()
 */
add_filter( 'wp_nav_menu_args', function( $args ){

    if(    isset( $args['menu_class'] ) 
        && 'menu genesis-nav-menu menu-primary' === $args['menu_class'] )
    {
        if( class_exists( 'Menu_With_Data_Attr' ) )
        {
            $args['walker'] = new Menu_With_Data_Attr(); 
        }
    }

    return $args;

});

to add the Menu_With_Data_Attr walker to the wp_nav_menu() used by genesis_do_nav().