Don't worry, this "simple" sentence really is rather difficult to translate!
Informal, i.e. spoken German: Als wir im Restaurant waren, haben wir uns hingesetzt.
Formal, written German: Nachdem wir das Restaurant betreten hatten, nahmen wir platz.
To correct your version: Als/Nachdem wir in das Restaurant hineingegangen waren, haben wir uns an einen Tisch gesetzt. (also correct)
One of the various problems with this sentece is that we (or I?) usually use "ins Restaurant gehen" in a non-specific way as opposed to "zu Hause etwas essen". Here, you're talking about one specific restaurant. Therefore I'd say "in das Restaurant (hinein)gehen".