I have exactly the same problem. I’m using WP 3.9.1 and Polylang 1.5.3. My home page is set to show my latest posts and I have two languages: english (default), and portuguese. My permalink setting is set to “Post name”.
I don’t have any problem with the pagination in english. For instance:
http://sitename.com/en/page/2/
But if I try to access:
http://sitename.com/pt/page/2/
I get an error 404. 🙁 Please advise.
I have this problem too since WordPress 2.5! I’ve tried all fixes but I had no luck!