I have PDFs using many embedded fonts from many alphabets.
Should I expect them to be viewed without any problems on Kindle, or only a part of them will be supported (for the most popular alphabets)?
Every font contains the instructions to render all glyphs contained in them, so as long the software/device can use embedded fonts, you should expect every of them to work.
I've checked it on my Kindle Classic. I've used the test I've made long time ago and described on my blog: Using dynamic fonts for international texts in iText. Both of the test PDF's available for download have been displayed completely and correctly. They contain Latin, Cyrillic, Greek, Chinese, Hangul as well as more 'exotic' fonts such as symbols, Glagolic, hieroglyphs and mahjong. The tiny problems with Armenian fonts come from some error in generating the document - they are exactly the same as on my computer in Acrobat Reader.