what is wrong with we are going up to the restaurant? and what would be wrong with we are going up toward the restaurant?
"we are going up" should be accepted - if not, report it - but IINM your second sentence would, well, require a word for "toward" - namely, felé, which isn't present in this sentence.
but doesn't the hez connote "toward?"
No, it does not. "Toward" is "felé".
If you are going top down in the tree, the "felé" postposition has not been introduced yet. The question I have is how a seemingly general verb conjugation "felmenni" could mean "going upstairs" - does fel imply rising elevation?
Yes, "fel" means up.
"Felmegyünk az étteremhez." is a bit strange, but it makes sense if the restaurant is upstairs or if it's at the top of a hill.