According to the help center article How do I add or remove login credentials from my account? (emphasis mine):
You can choose Google, Facebook, Yahoo!, and other popular OpenID providers; create a new Stack Exchange OpenID by providing your email address and creating a password; or you can manually enter another OpenID address.
The page you get to if you follow the instructions looks like:
As you can see, the two things the dialog prompts for are email address and password. However, entering an email that isn't already registered gives this error:
So either the help center article should be changed to explain how to create an SE OpenID first or the dialog box should default to allowing users to register from that page. Assuming most people expect to create a new Stack Exchange OpenID when they are adding a credential to their account, I think the later option makes more sense. I envision the implementation being something like the Log in/Sign up tabs.