If polishing pastes won't take out scratches, they're likely going to need sanding anyway. Even a 'coarser' paste/polish would have to do essentially the same thing as sandpaper, with the same potential for creating new, finer scratches on the other clean steel.
Sometimes it doesn't have to be that bad anyway, with sanding. Take 'baby steps' back in grit, from the polishing pastes, until you reach a grit that will do the job. I'd start at 2000 grit (wet/dry), then back down to 1500 > 1200 > 1000 > etc as needed. Once the original coarse scratches are removed, go back up the same grit chain in the other direction, finishing with the polishing pastes again.
Another option would be to use a compound that's more aggressive for it's size, like diamond. If done gradually, over time, some scratches can be 'stropped' out of the steel, using diamond compound applied to a firm backing, like leather, balsa and other woods. If the scratches are deep, it will still take a long while.
FYI, I think the grit size for Flitz is around ~3 micron or so. I think Simichrome polish is around ~8-9 micron (both spec'd per their makers). If you're very lucky, the slightly larger grit of Simichrome might work a little better. Both are aluminum oxide abrasive. Even Simichrome won't remove a lot of noticeble scratches in steel, however.
David