True, the present structures were rebuilt in the C14th & C15th, but the entire Kremlin itself dates back to the C11th
St Sofia's Cathedral - which is built within the Kremlin walls - dates from the C11th, although it has been repeatedly renovated over the centuries. The Yuriev Monastery, the St Nicholas Monastery and the Antoniev Monastery (all outside the city) are all from the C11th too. So there is plenty of Russia's oldest architecture still standing in the area, and within the Kremlin too
I've been in that "Hotel Tourist" and it was truly horrible

There are several other hotels in Novgorod which aren't expensive, and they are better
You can have a medieval dinner in the Detinets Restaurant - it's in a former Guard Chamber of the Kremlin Walls (entrance from within the Kremlin, through a Guard Tower). The food and recipes are 'Old Russian", including roast duck, mead, etc. I wouldn't say it is really super, but the atmosphere is nice. If you prefer a modern restaurant, then Holmgard is good - it's in the large building built on the lawns in front of the Kremlin.