Permalinks causing pagination to fail

I’m having a problem with custom permalinks causing pagination to fail, i.e. trying to navigate pages leads to Error Page 404.

The problem goes like this:

Pagination only works when permalinks are set to Default and page URL looks like this: https://golovegreece.com/?paged=2.

Pagination doesn’t work (goes to error page) when permalinks are customised and page URL looks like this: https://golovegreece.com/page/2/

Any ideas how I can get custom structure to reflect first URL that works?

Thanks