Add New Page menu not shown to non-admin users

When we recently updated our wiki from 4.5.3 to 5.0.2, our normal non-admin users no longer are shown the "Add-> New Page" button. I'm not sure about how it's called in english, but in german it is called "Erstellen->Seite". So they cannot create new pages in that way.
They can however type the name of a non-existing page and create it that way. So the question is, why are they not shown that menu item.
So far the menu item only appeared when I gave wiki-level admin rights to the user/group.