I have a WCF service which is used synchronously, but its ConcurrencyMode is set to ConcurrencyMode.Multiple value, because the service is stateless actually. How much overhead does this mode impose? Does it make sense to change the mode to ConcurrencyMode.Single?
It doesn't really impose any overhead - other than the fact that the single service instance must handle concurrent access, it has to be 200% thread safe - and that's fairly tricky programming.
Switching to ConcurrencyMode.Single makes programming it simpler - no more worries about concurrency in the service class. But it serializes all requests - only one at a time can ever be handled and thus will become a performance bottleneck quickly.
You mention your service is stateless - so why not make it use the usually agreed upon best practice - not a singleton, but a regular "per-call" service class. In that mode, each request gets a fresh new instance of your service class, there's no fussing about multithreaded programming needed (all the multithreading is handled by the WCF runtime), you get concurrent handling of multiple requests - to me, that's only benefits and no down sides!