Go for it! As you acknowledge, the idea isn't completely groundbreaking, but it's a solid mashup of tried and tested gameplay elements with your own twist. I think that there is currently great potential for "pseudo retro" designs such as this - we now have the luxury of looking back on 8/16-bit history and learning from previous successes and failures. A great example of recent success in this area is Super Meat Boy - a lovingly crafted nod to the classics which is also an evolution of them.
I'll also point out that Game Maker is a great pragmatic choice for this project. You don't intend to push graphical boundaries, and so choosing the most productive development environment should be the priority - a modern computer can push sprites around in its sleep. I think that the increase in controller accuracy, screen resolution and the ability to easily apply effects like scaling/rotation (which were often impractical on classic hardware) is plenty to make a modern sprite-based game feel up-to-date.
Player controls/AI in this type of game is generally modeled using "state machines" - i.e. characters can be in one of several states (e.g. standing, walking, punching, flying through the air after being hit, lying on the ground after being hit, standing up..). They can transition between states either automatically (after a certain elapsed time) or as response to user input.
In fighting games a state is often tied directly to an animation, with transitions between states/animations possible at particular times/frames of animation. Most of the more intricate mechanics of fighting games, which competitive players strive to master (like combos, charging, alternate stances or cancelling in-progress attacks) fit cleanly into this model as well. This type of system can be represented nicely as a flow chart, which is useful as a design exercise and as an aid to planning artwork requirements (as opposed to sitting down and attempting to directly generate a list of the animations you will require).
I'll touch on implementation briefly, although this is a design thread, as you mention that you aren't entirely familiar. This is a game which can be implemented essentially in layers, with tangible, playable results at each stage:
- Character animations/states and transitions
- More complex spells, projectiles etc
- Skill trees affecting available abilities (i.e. unlocking state transitions, modifying damage values etc)
- Items, levels, game structure etc.
- More content (abilities/weapons/spells)
I would encourage you to begin implementation by building up functionality in this way, rather than by attempting to create levels and other content in the order you intend it to be encountered by the player in the finished game. I would also shamelessly borrow placeholder art for prototyping - you want to get into the meat of the controls and combat system as soon as possible. The game should still be fun to interact with if you strip out all story, stat advancement and skill trees, throwing the player into a single-screen arena with a few random enemies and fixed weapon/spells. This is the core of the game, and should be your focus.