In the minds of many Europeans,
before Canada was Canada, it was a vast wilderness, a cold and inhospitable place that nonetheless was the ancestral home of many Inuit tribes.
(A) before Canada was Canada, it was a vast wilderness -> "before Canada" is modifying "in the minds of many Europeans". Further, "vast wilderness" is modifying "a cold and inhospitable place..." It makes sense. Let's keep it.
(B) before there was Canada, it was a vast wilderness -> "Before there" is not modifying "in the minds of many Europeans". Incorrect.
(C) it was a vast wilderness that was Canada -> Same as B.
(D) Canada was what was a vast wilderness -> Let's re-read it,
Canada In the minds of many Europeans was a vast wilderness. It doesn't makes sense. Incorrect.
(E) Canada was what had been known as a vast wilderness -> "had been" incorrect use of tense.
So, I think A.