I can understand why a company would be worried about hiring a pure math PhD who doesn't have applied experience. I have known a lot of mathematicians, engineers, and people who have migrated in one direction or the other. It's not a guarantee that you can implement something -- or even develop something that CAN be implemented -- just because you can write a mathematical proof about it.
So: The piece that appears to be missing from your resume in order to get a serious algorithms job is proof that you can take things from the conceptual high-level pure math domain and implement them in code. If you want those jobs, the question you should ask yourself is: How can I fill that gap?
A postdoc is an obvious way to do that, which is why your colleague suggested it. You will be hired to do some specific implementation work which will result in products (papers) that you can point to, and you'll have someone who can be a reference and vouch for your ability to make those connections. That puts you in a very strong position.
If you are traumatized enough by your experience as a PhD student that even spending one or two more years in academia feels unmanageable, break down those two benefits and look for other ways to get them. You could implement some aspect of your PhD work in a code base that you put on GitHub. You could write about that and put it on ArXiv. You could reach out and make contacts with people who you think might have applications that your code base would be useful for, and ask if they would be interested in collaborating.
Just the first thing -- the GitHub repo -- might be enough to get you hired. If it's not, each subsequent step will put you in a stronger position. But each of those steps takes time. Again, this is why a postdoc is handy: You get paid.
The other option you mentioned was "usual" programming jobs. You say you are overqualified, but you also didn't mention your level of expertise in software engineering. Could it be that you are underqualified in that regard? Again, GitHub repositories will help you if you have that problem. You can also take one of those coding boot camps, but it is much harder to get placed with a company through one of those programs these days than it used to be. There are programs aimed specifically at people who did a little programming in their non-CS PhD program and now want an industry job that uses a lot of programming that might be helpful, though.
If you are already extremely proficient in programming, so the only problem is that you are overqualified, I will remind you that you can list your PhD as work experience rather than education. If you focus on the transferable skills and minimize the cachet you expect a PhD to have, it will probably read less to a hiring manager that you are overqualified. But I suspect, given your background, that it's more likely that you are simultaneously too expensive to hire (because of the PhD) while also being underqualified in other important areas (ie with practical experience collaborating on large code bases) for the lower-level software engineering jobs.
From the perspective of a hiring manager, the PhD can mean you will require a higher salary due to company policy, or because they expect you to negotiate harder because you have the degree. The PhD can also mean that you'll ditch this job as soon as you get one where you can use the PhD, which is expensive because replacing and training people takes a lot of time. I haven't been on a hiring committee for machine learning jobs in industry but I've had an inside look at several hiring processes over the years and the jobs tended to go to someone who would grow into the role rather than the most highly qualified candidate because they were expected to want to stay longer in the position. If you're really good -- much better than the other people applying -- the hiring manager is more likely to be willing to take that risk. If you have an equivalent level of practical experience with software engineering to someone without the PhD, they may not be willing to take the risk. (Also, please understand that not all hiring managers will feel this way -- a minority will view a PhD as a plus no matter what.)
I hope some of this is helpful for you.