The direct answer to your questions is that Makecert.exe is an utility which is installed either from installing Visual Studio or Windows SDK or direct download from Microsoft sites. A Windows Azure VM sure not to have this makecert.exe because it is not part of base Windows deployment and if you want to use/run Makecert in Windows Azure VM you really need to add in your project and deploy it.
HOWEVER,
If you have a need to deploy a certificate to Windows Azure you really don't need to generate it on fly (i.e. using Makecert.exe) because there is other easier way to do it. You just need to add (or deploy) your PFX certificate to your Windows Azure Service -> Certificate section and when you VM will be initialize, the certificate will be provisioned to your Windows Azure Role (Web or Worker or VM) so there is no need to add Makecert.exe with your project and then use Startup task to run it.
Instead of depend on Makecert.exe or any other method to have certificate in your role, i would suggest using above method which is actually designed for such requirement. If you don't know how to deploy a certificate to your Windows Azure Service either directly to portal or using PowerShell, please let me know..