For most users, WordPress SEO and Polylang should work correctly together, provided that you use pretty permalinks and don’t set the language from the content (yes, although I like this feature, I must agree that it does not play nice with all plugins).
For what is related to sitemaps, the basic idea of the WPSEO compatibilty code included in Polylang is to mix all languages in the same sitemap. This works great when setting the language from the directory name in url. This is also what is generally done in other compatible sitemap plugins such as XML sitemap and Google News feeds. I like this approach as it eases the task of the website admin.
This should have worked whatever option you choose to set the language (directory name, subdomain or multiple domains), but Joost de Valk and I don’t share the same view and WordPress SEO explicitely removes from the sitemap all the content from subdomains and domains which are not the one defined in your WordPress general settings, thus keeping only the content from the default language 😦
I had thus to work around this and Polylang 1.6.4 introduces a separate sitemap per subdomain or domain when using WordPress SEO (while keeping the unique sitemap in other cases). If you have subdomains and prefer to have only one sitemap, XML sitemap and Google News feeds seems to be currently a better choice.
Polylang 1.6.4 fixes a few other bugs reported by users during the past month.