Are these 5000 404 Errors a problem?
No, not in terms of SEO. The page has been deleted, there is no other page that has replaced it, so it simply does not exist anymore. It is a 404. This is a natural life cycle for many web pages, a 404 itself does not hurt your SEO. (The fact of deleting the page in the first place, if it was a prominent page, is what potentially hurts your SEO.)
Should I use a 301 redirect pointing to a page with the message, "This page has been deleted"?
No. A 301 tells search engines that the page content has moved to a different URL. It has not; it has been deleted.
The 404 page itself should inform the user that "This page has been deleted" and provide information to help the user. Perhaps create a custom 404 specifically for this purpose.
Do I have to delete these deleted URLs from the sitemap?
Ideally yes. Whilst the sitemap itself is only advisory and won't directly hurt your SEO by having URLs that return a 404. It is certainly sending the wrong signal to search engines and is only going to perpetuate the 404s. However, 5000 x 404s might result in wasted "crawl budget" - Google is going to waste time crawling deleted URLs, rather than the URLs that really matter. So, this might have a detrimental effect on how quickly new URLs get indexed.