> Gerðu þeir með sér hina kærustu vináttu.
> They made between themselves promises of most sincere friendship

Yes, they agreed to be the firmest of friends, cf. Zoega 'gøra' (3)
"contract" g. vináttu, félagskap.

> hvar sem eg er staddur
> where ever I am

That's right, "wherever I am", "wherever I happen to be". Older
spelling and grammar: 'hvar sem ek em staddr'. 'staddr' is originally
the past participle of 'steðja', but has enough idiomatic uses for
Zoega to give it a separate entry of its own (as with 'búinn', past
part. of búa').