あなたの質問に対する直接の答えは、Makecert.exeは、VisualStudioまたはWindowsSDKのインストール、またはMicrosoftサイトからの直接ダウンロードのいずれかからインストールされるユーティリティであるということです。Windows Azure VMにはこのmakecert.exeがないことを確認してください。これは、基本のWindows展開の一部ではないためです。また、Windows Azure VMでMakecertを使用/実行する場合は、プロジェクトに追加して展開する必要があります。
ただし、証明書をWindows Azureに展開する必要がある場合は、他の簡単な方法があるため、証明書をオンザフライで生成する必要はありません(つまり、Makecert.exeを使用)。PFX証明書をWindowsAzureサービス->証明書セクションに追加(または展開)するだけで、VMが初期化されるときに、証明書がWindows Azureロール(Web、ワーカー、またはVM)にプロビジョニングされるため、プロジェクトにMakecert.exeを追加してから、スタートアップタスクを使用して実行する必要があります。
Makecert.exeまたは他の方法に依存して証明書を自分の役割に含める代わりに、実際にそのような要件のために設計された上記の方法を使用することをお勧めします。ポータルに直接、またはPowerShellを使用して、Windows Azureサービスに証明書を展開する方法がわからない場合は、お知らせください。