See, part of what HMs were mean to do was involve Pokemon in the game world in a context outside of battling. So replacing with items isn't the solution I'd be looking for.
Instead, every Pokemon would innately have HM value. For instance, the majority of Water types would naturally know how to use Surf outside of battle. Pokemon with wings could Fly, strong Pokemon would know Strength, etc.
This way, you don't lose out on the one major value HMs bring to the table, and you prevent HMs from infringing on the combat mechanics. Translate the actual HMs into TMs and you're done.
"We have no loofas in the Palace of Wisdom" - John Morrison
Like I stated in another thread, my only problem with HMs, is that they take up a moveslot. I feel as if though, if a Pokemon has the ability to learn a HM, that it should act as some kind of passive overworld ability or something.
I would rather make their use easy and quick and efficient while in the field and make it a little more varied.
Say for instance, you are traveling on route 205 and there is a tree to be cut down that goes to a side path to an item. All you need to do is press A in front of the tree. If you have a Pokemon with Cut, the tree is cut down, no prompts or menus at all. If you have no Pokemon with Cut yet, then you get a short phrase telling you.
Same goes for moves like Strength, Rock Smash, Waterfall and the like. When each move is taught to a pokemon for hte first time, it will tell you how you can use it and where, and in the TM screen, you can select a spot to retell the into.
Moves like Fly, Dive and Dig can be used with the shortcut Y if a Pokemon knows it in the party.
There could be a tangle of vines, vegetation or something that would require you to cut a path into which could also uncover a cave entrance, hidden item ball, pokemon and like. Hell, just let me cut down regular grass again!