Floor buffer with rotary brush and a good cleaner or degreaser. If they are bad may need to be grinded off or they will be sealed in forever if you clear seal. A colored coating would just hide them.
Slow speed floor machine with a black pad and a little bit of laundry detergent in water is what we used to remove the tire marks from my shop floor before sealing. My floor looked as bad or worse when we started.