My opponent has Mageseeker Warden on a battlefield. I try to play Baron Nashor. If no Baron Pit exists yet, is Baron legal to play? If so, where does Baron go?

Yes, it is legal. Baron's effect is a replacement effect: it replaces the event of him entering the location you played him to with him entering the Baron Pit instead.