Today I succeeded installing and running Microsoft Dynamics NAV on Azure. I followed the provided walkthrough you can find here:
http://msdn.microsoft.com/en-us/library/dn168989(v=nav.70).aspx
I deployed it from my Windows 8 box. This helps, because it has most prerequisites already on board. I only had to install the Azure Powershell (find it here under command line tools)