Hi Tobias,
Profile menu item is available even to a user with ‘subscriber’ role, which has only ‘read’ capability. If this menu item is not available for your users, some plugin blocks it.
You may try deactivate them all, test, then activate plugins back one by one with new testing to isolate a reason.
