Is there a way to remove a root from under a walkway to bring it back to level without getting the walkway redone?
Saturating wood with saltpeter produces an oxidizer, allowing it to burn while buried. In ancient days gone by you would drill a hole in the stump, fill it with saltpeter from the corner drug store, then light it after a couple days. The stump and roots would all burn. In these more enlightened times you're probably violating some civil ordinance by doing it. 

If safety is the only priority you can cut out a section of the walkway directly above the root with a wet saw. (Either rented or a contractor) With the pavement lifted out of the way you can dig out the root with hand tools then pack the void with an appropriate base. If you've lived a virtuous life the original section will have remained intact, otherwise you'll need to repour the small section. This will leave a visible repair, but you can definitely do it below $2,500.

FYI, if you look in the Yellow Pages you should be able to find a masonry supply yard nearby. There's an excellent chance that they'll carry the aggregate used on your walkway.