It really sounds like your header containment has changed. Go into the customizer and select Header. I think in your case, you’ll want to pick Header Main. What does it say for Layout? You will see three options: Full Width Contained, Full Width, and Contained. Play with those three settings, it sounds like something was reset.
Otherwise, it could be a number of other things. For one, the font could be too big, the spacing to wide, or number of items in the menu relative to those things. You can also look at these things in the Customizer. There is also the possibility that there is a widget that matches the background color. You can’t see it, but it’s taking up space in the menu.
