Do you use Confluence Cloud or on premise?
If you use the server version please go to the permissions (Space Tools in the lower left corner and than permissions) and see that the option add is checked for pages.
And you don't the any plus icon (+) on the left sidebar?
I do have that option but just wondering how I would get an option in the header. I think something is wrong.
You can't (according to my knowledge). You will have to use the sidebar for that.