Random ideas:
Firstly make the map MUCH,MUCH bigger.... 40x40 sounds like a good start.
Then with the 40x40 area add terrain (by terrain I mean x12-y19 could be a jungle part of the map, x13-y38 could be a desert) you get the picture...
In each 'biome' of the map could contain different monsters (For example; the 'Jungle' biome could contain 'monkeys'. The 'desert' biome could contain 'scorpions').
In between battles I'd like to be able to see your 'healthbar' regenerate 2 bars every time you move throughout the map without encountering a enemy.
More achievements and statistics in players stats?
(Achievement) For example; {{{Achievement #02 'Kill a cow'}}}
and...
(Statistics) For example; <[Total cows killed: 509]>
You could add player currency, money and shops. Everytime you kill a enemy it'll have a 75% chance of dropping Gold? Shops could be scattered across the map? Buy weapons and armour. Getting achievements gains you more gold? Gold loot scattered across the map?
As you wonder Further and further away from the spawn point monsters get harder to kill? But you get MORE money from monsters? Shops contain more valuable items if a shop is further away from the spawn point?
Magical/fantasy monsters? Other players/NPC's that you can trade with?
Extra levels; (Punch level, Kick level, Evade Level. Which can be 'level'd up' to improve combat)
One more thing I'd like to see the player have more than 1 life pr game. Maybe 3?
Well... That basically all I've got at the moment, see if you can add a few of those things in
.