You know, maybe this could be included into the quests.
Part of the tutorial could be playing with the starter deck of every element to show new players the strengths and weaknesses of the elements. Then, only after playing (but not necessarily winning) every element will a player be allowed to choose a Mark and the starter deck for that Mark and go on to regular play.
