The following steps allowed me to get the Windows 8 Mail app to talk to an Exchange server which uses a self-signed certificate:

  1. Open up Internet Explorer in 'Administrator' mode
    1. Go to the Windows 8 desktop
    2. Right-click on the Internet Explorer icon
    3. Highlight 'Internet Explorer'
    4. press Shift-Ctrl-Enter to launch IE in 'Administrator' (elevated permission) mode
  2. Browse to the Exchange server's Outlook Web Access page – eg. https://yourexchangeserver.com/owa (broken link)
  3. Ignore any warning about certificates – click on 'Continue to this website'
  4. Click on the red certificate warning in the address bar certificate error
  5. Click on 'View certificates' Untrusted certificate
  6. Click on 'Install certificate' button
  7. The 'Certificate Import Wizard' appears
  8. Leave 'Store Location' as current user
  9. Select 'Place all certificates in the following store', and click on the 'Browse' button to select 'Trusted Root Certification Authorities' Certificate import wizard
  10. Complete wizard
  11. Click on 'Yes' to install certificate
  12. Close IE and reopen (in non-admin mode) to confirm when browsing to the OWA URL that you no longer are warned about an invalid certificate

You should now be able to use the 'Add an account' to add your Exchange account.