Part of your error is in the tool you used. You may want to convert them (depends on what you're doing - it's more likely you'll want to go the other way and have your GPS points projected to your contour CS), but that's not what the Define Projection tool does. That tool is intended to be used when you know the projection the data is in, but it doesn't (no definition file/etc.). The tool doesn't change the CS, it just names it. It's kind of like a file extension - you can rename a .zip to a .jpg, but that doesn't make it so; the data is still zip file and in that format. Project is the tool (or one way) to change it, but to use that you must first know what you are converting it from. Related/duplicate question (at least for this part): Layers with same coordinate system should align/overlap but do not?
The first clue about what CS the data is in comes from that status bar where you are looking. Another part of your error is here - that label of Decimal Degrees is simply the display unit for the data frame, not the actual unit of the data. It can be changed on the General tab of the data frame properties (if your data is in meters and this is properly defined, but you want to see feet, you can change that here). But the file you have is in some unknown units - Arc knows how many of them there are, but not what they are - that is until you told it that it was degrees by defining a CS whose units are degrees.
Back to the clue part, you can look at the numerical format of the units and get clues to what the real unit is. If they don't go over 180, it's probably lat/lon degrees. UTM zones use a coordinate system designed to keep everything in positive values. To that end each zone sets an 'arbitrary' origin 500km west of the central meridian of the zone and a zone is about 600km wide at the equator - your second image shows a value of 671k, so this is certainly feasible (your data would be in the eastern half of that zone). For northings, the value is meters north of the equator in the northern hemisphere or the south pole in the southern. A quick Google on Malawi Africa to the Wikipedia page, and from there to GeoHack gives UTM coordinates of 36L 575612 8457692. That northing is pretty close to the number you have, so there's a very good possibility that UTM zone is the correct projection for your data.
If it weren't, or the numbers were very different, you could be looking at a localized projection. A good place to start looking (other than the data source) for other options is the EPSG Registry. I put Malawi in the Area description search and it comes back with eight results, only two of which are projected coordinate systems.
There is also an ESRI help page about identifying unknown coordinate systems.
Once you have identified a possible CS, as Stephen suggested and is also covered in some other questions here, you can then compare your data to known data in that area to see if it lines up. If it does, then you can use the Define Projection tool to set it.
