So finally I called the Apple Support: He could help me as follows:
We set up a hotspot connection from my iphone to my mac. The phone was not in my local WiFi network! Then sending emails from and to icloud worked fine. As my wife had the same problems from her MacBook it could not be a setting of my mac - it must have something to do with my (new, I admit) router, a Speedport W724V from German Telekom. The Support advised to ask them as he did not know the router hardware well.
Short time afterwards he called me again, saying that a colleague of him heard about a whitelist of "allowed SMT servers" that is kept on the Speedport W724V router . I should have a look there.
In fact, the router the mail had issues with, namely "p01-smtp.mail.me.com“, was not listed in that list. After I added it, everything worked fine again. Stupid Telekom I thought. But after a second look, I found the entry "smtp.mail.me.com“ in the whitelist, to Telekom _did_ think about Apple, but Apple decided to use a different SMTP server in the mail app than it used to used. That is stupid, I think.
What is more annoying is the fact that on the page http://support.apple.com/kb/HT4864?viewlocale=de_DE the old SMTP server is the listed as the proper one. I already tried to change the SMTP server in the Mail settings to be either one of the two, but that of course did also not work, as Mail _always_ uses its own icloud server, in this case "p01-smtp.mail.me.com“....
Grrrr....