Problems connecting to iTunes store
I solved the problem with help from Apple support. The resolution in my case was simple enough, if perhaps a bit drastic: I had to reset the network settings.

Settings → General → Reset → Reset Network Settings

Warning: This reboots the phone, and you have to reenter any WiFi settings for networks you use. Be sure that you have the needed passwords before doing so!

This may not be the solution for you, if you have this problem. Be sure to consult the three articles linked from the question first! But the network settings reset is an option to keep in mind if all else fails, and before you contact Apple Support yourself. (I don't know why this is not listed on the Advanced … page.)