Understanding UTM coordinate syntax in Zambia?

I suggest to use UTM zone 35. The points fall inside the Zambia borders:

For UTM Zone 34 and 36, the points would be outside of the country, shifted horizontally into the next UTM zone.

The "Grid" could be some local kilometer-wide grid for finding streets and places. It seems to be build from a Northing coordinate, "c" and an Easting coordinate in kilometers:

This works for most points, except the northernmost.

Zambia falls in the UTM zones 34 and 35 (quick check on Google Earth). The grid most probably refers to a grid of map sheets.

Looking at the X in the coordinates, the points should fall within zone 34. The X in zone 35 does not go over ~684,000 (again, this is based on looking at GE).

My answer is based on the information you provided and looking at GE.

Your best bet is to get back to the source of the data and get accurate info.