REST services are simply stateless http request/response web services, there are no problems at all to call them from WCF.
in fact when you use ESRI web APIs (all of them: Javascript, Silverlight, etc.) they simply hide you the http request building process.
In fact when you access an ArcGIS Server REST service from the web interface you can send any REST request also from there, simply filling the appropriate fields inside the web form: you can make spatial queries, enlist features, and so on (sample here).
the only thing you have to know is the URL request syntax and eventually the JSON data format to send to the service (and obviously the JSON response data format): you can learn all these things from the ArcGIS Server REST API documentation (sample here)
So from a WCF service you can query an ArcGIS Server REST service simply building the right http request using for example a System.Net.WebRequest object and parsing the response. and yes you have to do it programmatically (so this is why ESRI build us the Js/Silverlight/etc web APIs...)