か marks "どういうわけだ" as a discursive insertion (or just an interjection). If you take this part out, the main sentence is still grammatical.
で marks the instrumental case, "with/at/by ...". "史上最年少で" means "at the youngest age in history".
Yes, the -te form can mean "since". I think it's a type of the so-called ablative cases.
The first に in "新人に" marks the dative case, "to ...". "新人" (newcomer) is one of the categories of the journal to which you can send your novel. The second one in "大賞に" is similar. It means that the sent and evaluated novel rose up to (and won) the grand prix.
"それが" in this context is more like "but", "for all that", rather than the literal "that is/was".