Hi kc,
This is indeed something KM can handle. Here's an example macro that should get you started. The actions colored with aqua are comments explaining what's happening in each part of the macro:
Auto File Rename.kmmacros (8.4 KB)
Results
Before
After
All you should need to do is set the path to the folder you want KM to watch at the top of the macro. You shouldn't need to use Hazel at all for this, but if you'd prefer that, there are ways to make KM work with it as well (you can see this thread for an example if you're interested). Good luck, and feel free to ask any follow-up questions.