Мне кажется тут проблема может быть из-за двух причин:
1. Потребление реле (оно дает пик при включении ибо тоже индуктивная нагрузка).
2. Потребление мотора на старте.
С первым бороться "программно" - не возможно - нужно менять схему - уходить от классических реле в твердотельные (по сути дела полевик с оптронным управлением), или просто полевик ставить.
Со вторым бороться "программно" - можно - ШИМ, но, на реле - тоже трудно - не те скорости переключения, что обычно требуются для ШИМ.
Т.е. я бы нашел сначала подходящий силовой полевик (их иногда драйверами называют) или твердотельное реле с приличной скоростью срабатывания. Но твердотельное - это в первую очередь гальваническая развязка, которой с общим блоком просто нет, т.ч. твердотелка - немного избыточно.
Ну а дальше делать плавный запуск исподльзуя ШИМ.
+ еще надо знать схемотехнику блока - в некоторых дешевых БП вся обратная связь (по всем напряжениям) выстроена по цепи +5В. Это тоже может давать крайне неприятные эффекты при переходном процессе (старте движка).