No, they should not. It is encouraged you leave a comment (and undownvote if/when the user improves their post). But it is never mandated--and I really doubt it ever will be.
Privacy
Votes are supposed to be private. If a comment is forced on a downvote, it's pretty easy to figure out who did it by looking through the comments. And users can get pretty vengeful.
On StackOverflow, over a span of two days, I once downvoted ~50 bad posts, leaving a comment. I had 4-5 cases of revenge downvotes, 1-2 cases of enough "revenge voting" to trigger the auto vote invalidator, and a bunch of angry comments. Users should be free to vote without having to be afraid of this.
Smoothness
Voting is integral to the SE system, thus the process of downvoting needs to be smooth. A user need not have to jump through hoops to downvote, people will downvote less if it takes more time to do. And we can't have that, people need to downvote.
As for your answer that was voted down, it really should be a comment (I converted it). A few points:
- Really short answers are discouraged here, it's always better to provide an intuitive explanation
- Answers that only provide a link are even more discouraged--due to concerns of link rot/etc. You should summarize the link in your own words (few paragraphs-is) so that the answer can stand alone.
- Comments asking for improvement should go in the comments to the question. Click "add comment" out there.