I found the issue in my case - I have overlooked that the user is assigned to a global role with the permission allowed.
So, to explain it - the permissions are set on various levels or layers. It is like an onion. And if there is a deny permission or no permission set on any of the levels, better safe than sorry, the denial permission is applied.
So, in this case you allowed to create pages on the page level. But now the system looks at the higher level "OK, user can create page but what page type should I allow? All? Or some particular only?" And now, there is no allow permission set for content module (all page types) nor any particular page type is being allowed. So, system says "I do not know what page type to allow, the permissions are not set, better safe than sorry, creation denied!".
I hope it makes sense now and I am sorry for all the confusion. I got trapped with the global role and provided you with a false information!