What type of fan?
If it is an axial fan or a low pressure centrifugal fan you will not have problems with a contactor.
If, on the other hand, it has a turbine with a lot of inertia and a large diameter, a standard motor protection will not work well, the thermal protection will trip. In this case, I recommend using a soft starter, cheaper than a VFD.
My experience is that Siemens Sirius starters work well for those types of loads.