Archive pagination causing 404 with permalinks structure

Hi there,

Somehow my archive.php is causing some problems because I’m using /%category%/%postname%/ as my permalink structure.

The next_posts_link() redirects to category/page/2: which causes an 404 error.
After changing my permalink structure to /%category%/ the pagination works fine, but I can’t access any single posts or pages.

I’ve installed several plug-ins of course. The one that could affect the permalink structure is Yoast SEO, but after deactivating it still doesn’t work.

Anyone knows what this problem can cause?
Thanks in forward!