Apex - Converting Map to a string for REST response?

RestContext.response.responseBody = Blob.valueOf(JSON.serialize(locations));

JSON can handle almost any data type, including maps that include serializable types. The exceptions to this rule are items that can't be serialized, like SavePoint, SObjectField and so on.

If you really want to convert a Map to String you can do it by using String.valueOf()

Map<String, Integer> mapVal = new Map<String, Integer> {'zero' => 0, 'one' => 1, 'two' => 2, 'three' => 3};
String mapString = String.valueOf(mapVal);

I suspect what you want to do is really convert to JSON, which in that case you would do JSON.serialize as sfdcfox suggested.