Step 1: Set up a coordinate system with the starting point at the origin $(0,0)$ and north as the $+y$ direction, east as $+x$.
Step 2: Walk 5 km north: new position $(0,5)$, still facing north.
Step 3: A right turn while facing north points the man east (clockwise from N is E). Walking 3 km east: position becomes $(0+3,\,5)=(3,5)$, now facing east.
Step 4: A right turn while facing east points him south (clockwise from E is S). Walking 5 km south: position becomes $(3,\,5-5)=(3,0)$, now facing south.
Step 5: A left turn while facing south points him east (counter-clockwise from S is E). Walking 4 km east: position becomes $(3+4,\,0)=(7,0)$.
Step 6: His final facing direction after this last left turn is east, and his last leg of movement itself was also along the east direction, confirming the result.
Correct option: East