I’ve check your WordPress Admin.
You’ve change The Permalink structure, which is I wouldn’t to change that.
I’ve test the Theme (local & on server) using available permalink structure options in WordPress, there is no problem. The pagination works perfect.
Can you please only use available permalink structure options in WordPress ? If it doesn’t work, please try to disable all plugins, this may caused by a plugin.
Please let me know the results.