I'm glossing over some details in what follows, but I hope this will get you pointed in the right direction.
The problem is that the link on the dashboard just uses the URL stored in the certificates_generatedcertificate MySQL table at the time that the certs are generated. That value appears to have the hostname set to 'localhost', which always points to whatever computer the web browser is running on. Since the user's own computer is not a web server with a downloads folder, the certificates can't be found.
I'm not sure if I'm going to be able to help much, as I haven't tried serving certs off of the edx host; I've only set it up to upload certs to s3 and then serve them from there. But, I suspect that your edx server doesn't know its internet hostname, and so it's branding the certificates incorrectly. If you run 'hostname' at the command-line, it should return the name of the server that users type in their browser to reach your machine. If that looks correct, then the next thing to look at is your settings in /edx/app/edxapp/lms.env.json and /edx/app/edxapp/cms.env.json. Unfortunately I don't know what the local URL parameter is in the .env.json files, and I don't have my devstack handy to check. But I'm pretty sure you can find it fairly soon.
Once that's sorted out and your host knows what its name is, you'll need to either regenerate your certs or fix them. Regenerating is easiest - just delete the certificate_generatedcertificate rows for the course in question, and rerun the ./manage.py ungenerated_certs.
If you want to fix them, you'll need to patch up the 'download_url' column in the certificates_generatedcertificate table in MySQL. But beware that the default cert template also prints the verification page URL right on them, and that's likely to be wrong as well. So an in-place fixup may be unsatisfying.
Hope this helps. Good luck!