It's OK
But going to HR for a promotion is probably about as useful as going to Facilities and Maintenance for a promotion. HR should only get involved if the company is illegally discriminating against your promotion because you are in a protected class. Otherwise, HR has pretty much zero business telling business units whether to promote a particular candidate or not.
Perspective
Getting a promotion is very much like getting a raise: it all boils down to perceived value. Obviously, you think your value is higher than your boss does. But let's be honest: it's not just your boss. If other managers around the company thought you were overqualified for your current title, they would be clamoring to steal you away by offering you a promotion. The fact that the promo committee declined on a technicality pretty much tells you that they would have declined a technically perfect submission too, but without any face-saving excuses for you. They are trying to let you down easy. If the committee thought you were ready for the next level, no technicality would stand in their way.
Strategy
As you note, switching companies will be the most expensive move, because you are trying to build up credibility. So unless you are really unhappy with your current employer, or you run out of other options, that should probably be your last resort. And, as you say, your current team knows you the best. But, there should be other teams that know about your work as well. If not, then you should pursue projects with cross-team visibility and relevance. Frankly, for the level you're talking about, it isn't enough for your boss to think you are ready for promotion. Lots of other people have to think so too, and that depends on them seeing you in action. If they don't see your work or your professional opinions, or your documentation or your teaching influence or mentoring skills, then how are they going to form the opinion: "Thomas is really ready for the next level"?
The truth is, you need a boss that believes in you as much as you do. If you want to get to the next level, you need to find that boss. Obviously, it needs to be someone that you can build good rapport with. But it also needs to be someone who is also ambitious and looking to move up. Because that is the kind of person who will seek out opportunities for themselves, their team, and their star players. A manager that just sits around taking orders is not moving up, nor are they helping their star players (if they have any) to move up.
Undercover Boss
This means you need to shop around not by looking for open positions on teams, but by identifying the individuals that you think would make the best boss. Maybe that person is a Director or Sr. Director or VP. Find out what they are working on, find out how important those projects are to the company, find out how well they are regarded by other folks, other teams, upper management, etc. Nobody is going to score 5 stars in every category, so you have to make some judgment calls about which set of trade-offs will produce the best result.
Once you've identified one or two folks, see if there is anyone you know in common that can make an introduction. If you must, cold-call them by dropping by their office and seeing if they will agree to put you on their calendar for 30 minutes of coffee. When you get the meet, explain to them that you have lofty career aspirations, but you need the right opportunities to get there; you need the right projects, the right team, the right mentor, and tell them why you decided that they might be the best candidate. Let them know what important projects you've worked on that they might recognize, tell them you are constantly improving your skills and pushing the envelope, and you think you can bring some real strength to whatever team or project is center of mind for them. Explain that you just want the chance to show the company the full value which you can bring, that you've been under-utilized thus far, and if you just got a spot on the A squad, which this new mentor obviously built, that you can bring home some big wins for the team, for the organization, for the company.
A good potential boss will recognize and appreciate some boldness and ambition, but you really need to have some outstanding work to back it up, and probably a few folks you can name-drop that will put in a good word for you if they ask around.
Right Now
While you are finding a potential new boss, you should work to raise your profile. If your company has any public discussions about technology directions, best practices, developing trends, etc., you need to have a voice in those discussions. If you really think you are at the next level, this should come naturally and you should already be doing these kinds of things. You should be educating your team regularly by disseminating and encouraging best practices. Your team should find you to be the strongest but fairest code reviewer. They should regularly find your documentation answers questions they didn't know they had. They should be pointing interns and newbies your way to explain difficult concepts and offer mentoring and guidance. If they aren't, you need to demonstrate that you are willing, able, and good at all of those things, so people start doing them.
Team members should regularly be coming to you for help on their projects, including projects that involve other teams. You want folks from other teams hearing stuff like this at standups: "Yeah, we couldn't figure out how to get the service started, but Thomas unblocked us." "Oh, is Thomas on the project?" "No, but he's our go-to guy for the hard problems." That means you need to donate work to projects that you aren't directly assigned to. Lots of little things like this will help raise your visibility both inside and outside your team. When you go talk to the new boss, the best intro would be: "Yeah, Thomas...I've heard good things about you." Do what it takes to earn that response from lots of people. You never know who your next best ally will be.
