Note: This article applies to retired ArcGIS versions 10.2.x. Later versions of ArcGIS may contain different functionality, as well as different names and locations for menus, commands and geoprocessing tools.
No, it is not possible to directly export an ArcGIS for Server map service to a shapefile in ArcMap. Map services must initially have a Geoprocessing capability enabled, and have access granted to various tools and frameworks that allow analysis and management of geographic data.
However, users can add the map service into ArcMap and use the Distributed Geodatabase toolbar to extract data from the service. This works if the map service is enabled with Geodata Access from the capabilities list when the map service is published. The 'Extract Data' option is enabled when a valid service is added to ArcMap.