Converting between projected coordinate systems is easy, if the map projection algorithm is supported. In this case, you can either have the data project on-the-fly in ArcMap to the data frame's coordinate system, or create a copy of the data in the base map's coordinate system using the Project Tool (ArcToolbox, Data Management, projections and transformations).
The actual steps that occur internally when converting vector data between two projected coordinate systems are:
1. Coordinates converted from projected x,y to geographic lat,lon. 2. If the input and output geographic coordinate systems are different, do a datum transformation if one is specified. [In ArcMap] If not, treat coordinates as if they're already using the output gcs. 3. Convert coordinates to the output projected coordinate system.
If the input data is using a gcs, start at 2 instead, and so on.
I would use zone 36 North over 35 North, but the area is really too wide for a UTM zone. It would probably be better to map it in a conic projection, but Esri doesn't have any defined already.