I have the NS feature 'Allow Overage on Item Fulfilments' turned on, but when using WMS, I get the error 'The entered quantity cannot exceed the remaining quantity'. Is it possible to over-fulfil using WMS?

Yes, it should be possible. I don't believe there are any WMS System Rules for this either. Simply having the feature turned on should be enough.