I used custom settings for this, and it works well. I store the host name separate from the paths. This has the additional advantage that you can switch to endpoints on different environments fast.
Edit to add this example:
I use a ServiceCenterConfig__c list custom setting with two fields (Name, Value__c) to store general configuration information for an application.
One record is
[name="msc server", value__c="https://production.server.com"], another is
[name="msc path", value__c="/path/to/rest/endpoint"].
In a sandbox, I can set
"msc server" to another value, e. g.
"msc path" record stays the same for all environments.
This way, I can connect a sandbox to the same web service on a different environment than my production org. You could connect your UAT or integration sandbox to a staging or integration environment of the web service.
But since it's Summer '17 already, I would recommend to look into custom metadata instead of custom settings to do this.