fake it, going for some A* system would work well for sure, but its definitely way more complicated than it needs to be. keep it simple.
It depends on the game. If you had an enemy in Castlevania that would chase you throughout the entire castle (or a pretty large area), you'd probably need A*. Other than situations like that, there might be simpler methods.
Also, I'd like to mention, a "one size fits all" plugin would probably have issues with "fitting all." The A* would work for everyone, but everything else could vary quite a lot in how it needs set up for each game. I'm not sure how it'd work with the non-A* side of things.
I was talking in chat about this, and suggested Python as a possibility.
There's tons of stuff existing for sorting, and there's probably a lot for A* as well.
But the thing is that wont take into account your movement.
Yes it could find this node to that easy as pie, but how would it know when to jump, and at what speed?
There are ways to solve that, but with terrain in certain configurations, it gets tougher and requires a lot more work to set up the nodes in such areas. It's quite dependent on the layout of the level. I'm thinking A* might be the simplest part of the actual pathfinding.
Back to "one size fits all," since everything varies so much per game (e.g. platformer behavior vs custom movement), I'm not sure how well anything but A* itself could be turned into a plugin. There'd have to be a ton of planning on what EXACTLY it would and would not do. It wouldn't be a magic bullet. Even if a plugin was made, some things are so closely tied to individual games that an A* plus doing all the other events separately would be needed in plenty of cases. It is similar to how custom movement is still used in some platformers instead of the platformer behavior, except it would be an even bigger difference.