Whatever you use (abrasive paper of media blasting), it will be a good idea to dip everything into a citric acid solution as a final step to passivate the SS surface. The citric acid removes any free iron on the surface and makes it more corrosion-resistant. Many super markets sell a product called "Lemi-Shine" which is a powder used in kitchen dish washers to remove streaks on glassware. It is nearly pure citric acid. Citric acid solution is also good for cleaning brass cartridge cases. And it's not hazardous like nitric acid would be.

Baking soda (sodium bicarbonate) blasting is most often used for removing softer materials from metal, such as paint. I am surprised it would be abrasive enough to have much effect on SS.