When I saw the problem the first thing I did was contact web357 support after investigating they said the problem was falang related, I contacted the falang developer and he sent me the url of this page.
I would like to inform you that the new version (v1.2.10) of "K2 Multiple Categories" plugin resolves the issue with pagination on websites which use the Falang extension.