“My point is that had it been a federal decision to put him on the NICS, such as with a federal felony conviction, is it still true that there is no mechanism at the federal level to restore his gun rights?”
I believe that you are correct.
To point out the obvious then, it seems this would be a great way for a federal level politician to get pro-gun recognition. An Act that would “create a mechanism” by which those denied guns at the federal level (especially veterans, by VA bureaucrats), could have their rights restored. (And some pro-gun recognition, right before a close election, might make all the difference in the world.)
By itself, it would not restore rights, just make restoration by a judge possible. Only gun controllers are in favor of perpetual loss of gun rights when there is no logical reason to do so.