''She is Abyssinian and she is a sea-woman''
This line actually makes me even more certain they didn't go to axum but rather coastal area and interacted with coastal people.
They had pre-islamic trade links with Somali and Eritrean coast as well and there some pre-islamic refrences
Was Eritrea not part of Abyssinia? Wherever they travelled to/stayed, we know for certain those people were Christians and had churches.