Yet Another Related Posts Plugin is probably the most popular related posts plugin for WordPress. And since Polylang 1.0, both plugins work together!
Step 1: Go to YARPP settings page and in the “Relatedness” options metabox, choose ‘require at least one language in common’ for the Languages option. This will force YARPP to get related posts in the same language.
Step 2: In the ‘Display options for your website metabox’, choose ‘Custom’. You may have to click first on ‘copy templates’ if the option is disabled. Then choose the template file ‘Multilingual’. Don’t forget to save changes.
Step 3: Go on the frontend of your website and read one of your post. This step is mandatory as we need to execute the template file at least one time to register the strings that need translation.
Step 4: Go on Settings -> Languages -> Strings translations and look for the strings ‘Related posts’ and ‘No related posts’ and just translate them in the other languages.
Of course, to fit your theme and your exact needs, you can make your own multilingual YARPP template file, looking at the file yarpp-template-multilingual.php to see how it is done.
Thanks to mitcho for his support. You can also have a look at our discussion on the support forum of YARPP.