Under PowerShell 4 supplied with Windows Server 2012 r2 and Windows 8.1 you can run a simple command to create a new certificate in seconds.
New-SelfSignedCertificate -DnsName hostname.domain.comĀ -CertStoreLocation cert:\LocalMachine\My
In my case I created one for use in Exchange 2010 and it worked perfectly.