UTM is surely not the right projection. UTM 37 is centered on 39°E, and has a false Easting of 500000 metres to that. South of the equator, UTM 37S is measuring from the south pole to avoid negative values.
Apart from UTM, there was a Cassini-Soldner projection (possibly in feet instead of metres), and a 5 degree wide "East Africa War" transverse mercator CRS used in earlier times.
Using a Cassini-Soldner projection centered on 37°E/0°N with ARC 1960 datum, I get for your point in WGS84:
38.046282° East 0.059779° South (decimal degrees)
located about 43km east of Nkubu town.
Based on the documents linked in Convert Cassini-Soldner Projection coordinates from Kenya to UTM I suggest to use the following proj.4 parameters for a custom CRS:
For the central meridian 37° (valid 36°-38°E)
+proj=cass +lat_0=0 +lon_0=37 +x_0=0 +y_0=0 +a=6378350.87 +rf=294.26 +towgs84=-306,-6,-101,0,0,0,0 +units=m +no_defs
For the central meridian 39° (valid 38°-40°E)
+proj=cass +lat_0=0 +lon_0=39 +x_0=0 +y_0=0 +a=6378350.87 +rf=294.26 +towgs84=-321,0,-135,0,0,0,0
Ellipsoid parameters are taken from Clifford Mugniers article, Datum shift parameters were computed from the coordinate tables in the document by Gordon Okumu Wayumba
A shapefile should usually have a .prj file with the projection information.
For GDA94, there are different projections available:
EPSG:3577 Australian Albers
EPSG:3112 Geoscience Australia Lambert
EPSG:3308 NSW Lambert
EPSG:3107 SA Lambert
EPSG:3111 Vicgrid94
EPSG:3113 BCSG02
and GDA94/MGA zone 48 to 58. From those, zone 55 should be the best choice.
If you are still unsure, look up the extent of the layer, as reported by properties, metadata tab, and include it in your question.
Best Answer
1) Plugins > Manage Plugins. Enable GdalTools
2) Then:
3) Enter the source and destination SRS and the other parameters. That's it.