As mentioned, the first thing to check is that the compressor has an unload valve and that it is functioning properly. Sometimes people dont understand the purpose and believe unloaders are wasting energy, so they disable them.
In some designs, the unload valve is on the receiver and is normally closed (so that the tank hold pressure when the compressor is off) and the solenoid pulls in to open the valve for a few seconds when the motor is first started, then drops out again to let the pressure build. For those, there will be a timer in the circuit. Others have a normally open valve on the compressor head, and when unpowered, vent the compressor cylinder to atmosphere, then the solenoid is energized at the same time the motor is. The valve has a way to make it close slowly to give the compressor time to get to speed first. If you have this type, a distinctive characteristic is that the compressor makes a loud hiss whenever the motor shuts off as the valve vents the residual pressure in the head. With neither of these, the compressor will be difficult to start (assuming reciprocal or screw compressor here). If you don't have an unloader, talk to a compressor dealer about adding one first, because it probably should have one either way and that alone may solve the problem.
If you do have a functioning unload system and it's just a matter of too much burden on the power feed, a soft starter will likely do the job on this because from the sounds of it, the system CAN start it, it just causes too much VD from the starting current. But I agree with the others, increasing the cables or changing the breaker will not likely help and may make it worse. Those solutions would solve a VD at the MOTOR terminals if that were the problem, but not the VD on the entire system, unless the motor VD is making it take so long to start that the up stream transformer is saturating. If that were the case, you would likely also be getting nuisance overload tripping of the compressor (unless that did happen before and someone "fixed" it by upping the overload heater!).
VFDs are not always good on compressors, it depends on the type of compressor, the storage system and the type of lube system it has. Don't go that way unless you can engage someone with a lot of experience in successfully applying VFDs to air compressors.