Glad that you solved. Let me know if you face more issues.

The Problem is in K2 attachment SEF URLs parser and/or generator. If you enable the "Category id and title alias separator", the Download URLs must be yourdomain.com/menu-alias/ID-CATEGORY-ALIAS/download/id_hash (Like www.domain.com/menu-alias/10-category-alias/download/20_9e847hfurh4449589302dd89). But K2 is not generating SEF URL well in this case, it is generating www.domain.com/menu-alias/download/20_9e847hfurh4449589302dd89 (without the id and category alias separator that you enabled in K2 SEF advanced configuration). When you click it, K2 don´t understand the link and throw a 404 error.

I made a workaround code for that, to force append the category id and category alias separator to the URL. You have to include this code in category_file.php and item.php K2 template files (this way we don´t hack K2 core files):