I just happened to be crawling through this section of the-bootstrap recently for my own purposes, so I have an idea of where to look. Here goes.
The pubdate message is related to the Posted On date in the entry header (which comes from the appropriate partials/content-xxx.php file). The date comes from the_bootstrap_posted_on in template-tags.php, and it is using pubdate. There seems to be mixed advice about this. On the one hand, W3C says they're dropping it. No, we aren't. Yes. No! Maybe! And other sites have a mix of recommendations to use it or not. It appears to be related to RSS feed publication. I'm not sure if this should be kept or dropped without some further research.
The complaints about rel="category tag" are related to the category links at the bottom of the post. As best I can tell, the-bootstrap gets this by calling WordPress's get_the_category_list function. Sure enough, the code in WP is injecting this. This seems to be a known issue in WP (though one they've apparently chosen not to fix). There's a simple way to remove it here. http://www.whitneykrape.com/2011/07/quick-fix-for-relcategory-tag-in-wordpress/
The legend tag is around the Leave A Reply heading on the comment form. According to W3C, it should only be used as the first child of a fieldset, hence the validator's complaint. The tag is coming from the_bootstrap_comment_form_defaults in functions.php, specifically the title_reply and title_reply_to values. I'm thinking it should be removed given W3C's guidance. I'll try to put up a pull on github tomorrow.
Finally, the border warning is related to the Share/Save image in your footer, which seems to be coming from your Add To Any plugin, based on the class applied and the fact that it's pulling from addtoany.com. It's applying a border attribute to the img, which apparently obsolete.
Hope that helps.