Если у вас есть контроль за строительством службы, просто измените его целевой платформы .NET 3.5, и вы должны быть в состоянии установить его.
В противном случае, если служба была создана для установки .NET Framework 4.0, и на сервере установлен только .NET 3.5, я не думаю, что он будет запущен, если вы явно не переопределите его в файле конфигурации, который будет запущен под .NET. 3.5 (что я бы не рекомендовал).
В качестве альтернативы, я всегда рекомендую пользователям использовать WiX Toolset для написания инсталляторов для служб Windows вместо использования InstallUtil, поскольку InstallUtil - это настраиваемый, нестандартный инструмент Visual Studio для установки служб Windows, тогда как установщик Windows (MSI), утвержденный стандарт для оконных установок имеет встроенную поддержку для установки проверенных и проверенных служб Windows и дает вам больше контроля, например услуги по остановке и запуску и т. д.