When clicking on the properties of a windows service, you can set the start parameters. Would you rather use this to configure a Windows Service or use an app.config?
For a user, it's much easier to change the start parameters of a service than having to go and look for the install directory of the service, open the app.config and edit it.
You seem to have answered your own question...
It really depends on the usage scenarios of your service and the amount of configuration it requires.
As you said, startup parameters make it easy, as they are controlled directly in the same location where the service is managed. However, they are not self documenting and you still have to provide documentation on what makes a valid parameter. They also don't lend themselves to extensive configuration.
An app.config, on the other hand can be self documented (xml comments), all possible configuration options specified and you can have a lot of configuration in them.
Another other point to think about is the number of deployments. If the service is going to only ever run on a small number of machines, with expert users (who understand XML), I would lean towards app.config files.