The tops of the silver K-MAGs are painted. So what about spray paint?
Years ago I needed to add some, lets call it detail, to a item of clothing and I used spray paint out of a can. Once dry, it was machine washable and did not peel, crack or other for the time I had the article. I used a primer paint which comes in black, grey and white.
I think if you wiped the shoes down with acetone before painting, that you will get better adhesion because acetone is what is used to "prime" PVC pipe before gluing.