Strange thing about Amazon: Japanese books (offered on amazon.com and amazon.de) are not available for the standard Kindle although it's perfectly capable of displaying Japanese content. This applies to all books in Japanese. Which sucks. So contacted support concerning that matter ...
Fortunately there are alternatives: 青空文庫 (Aozora Bunko) offers Japanese books for free and with 青空キンドル (Aozora Kindle) you can easily convert them to beautiful PDFs. :)
To do that, take a book from 青空文庫 (for example this), scroll down to the ファイルのダウンロード section and copy the URL to the zip file. In our example that's:
http://www.aozora.gr.jp/cards/000311/files/2762_ruby_8768.zip. Head to 青空キンドル, paste the URL, change settings if you want (I recommend setting the 文字 to 大), hit PDF化, copy the PDF file to your Kindle and you're done. :)
Beautiful Japanese on your Kindle. What you may want to avoid, however, is using Japanese file names. They won't be displayed as expected, which I presume it's due to the FAT 32 file system.