Add within the output of

Use the arguments before and after:

wp_nav_menu(
    array(
        'theme_location' => 'primary',
        'menu_class' => 'nav-menu',
        'before' => '<span>',
        'after' => '</span>'
    )
);

To see how these arguments are used, look at the method start_el() in Walker_Nav_Menu:

    $item_output = $args->before; // 'before'
    $item_output .= '<a'. $attributes .'>';
    $item_output .= $args->link_before . apply_filters( 'the_title', $item->title, $item->ID ) . $args->link_after;
    $item_output .= '</a>';
    $item_output .= $args->after; //'after'