It is unclear. Both terms appear in one of Tolkien's earliest works on Qenya, and thus existed in 1916 before any of the Lost Tales were even written, but the specific meaning may have been added later, and because Tolkien would usually erase his original drafts, it's hard to figure out exactly when that was added.
Both names existed by 1916, likely without the final meanings
The first stage of Tolkien's writing, covering a period from around 1915-1916, consisted of a few scattered poems, some notes, some illustrations, and an extensive linguistic lexicon known as "The Qenya Lexicon".
Tolkien presumably left the Lexicon in England when being deployed, and so even though he would later continue to extensively revise it, a list he made based on the Lexicon when returning to England helps show which words must have been part of the original 1916 stage. John Garth explains this in Tolkien and the Great War.
JRRT is unlikely to have risked taking the lexicon on active service, and its state circa March 1916 may be broadly surmised by excluding all entries lacking in 'The Poetic and Mythologic Words of Eldarissa', a list copied from it probably soon after he returned to England (Parma Eldalamberon 12, xvii-xxi). Some details appearing only in that list are assumed to postdate the initial lexicon phase, and omitted here.
Tolkien and the Great War - Notes to chapter 6
John Garth then proceeds to provide an extensive summary of the state of the mythology as it existed at this point. Based on this, Tolkien seems to have came up with both of the names you're asking about, but only as descriptions of Hell; the character of Melkor did not yet exist and so it's unlikely that their later conception was already present.
Besides wonders, there are monsters in these pages too: Tevildo the hateful, prince of cats, and Ungwë-Tuita, the Spider of Night, whose webs in dark Ruamōrë Earendel once narrowly escaped. Fentor, lord of dragons, was slain by Ingilmo or by the hero Turambar, who had a mighty sword called Sangahyando, or 'cleaver of throngs' (and who is compared to Sigurðr of Norse myth). But there are other perilous creatures: Angaino ('tormentor') is the name of a giant, while ork means 'monster, ogre, demon'. Raukë also means 'demon' and fandor 'monster'.
The fairies know of Christian tradition with its saints, martyrs, monks, and nuns; they have words for 'grace' and 'blessed', and mystic names for the Trinity. The spirits of mortal men wander outside Valinor in the region of Habbanan, which in the abstract is perhaps manimuinë, Purgatory. But there are various names for hell (Mandos, Eremandos, and Angamandos) and also Utumna, the lower regions of darkness. The souls of the blessed dwell in iluindo beyond the stars.
Tolkien and the Great War - Chapter 6 - "Too Long in Slumber"
As best as I can tell from the commentary of edition of The Qenya Lexicon published in Parma Eldalamberon #12, the following seem to be the earliest surviving states of these two words. (Though even so, these could have been written later, as much of the original 1916 definitions were erased and written over.)
ANGAMANDU = EREMANDU. or (pl.) Hells of Iron
UTUMNA lower regions of gloom and dark (not same as MANDOR a place of torment).
Parma Eldalamberon #12, "The Qenya Lexicon", pages 31 and 99, reconstructed from the commentary
Both names with their final meanings existed by c.1917
Tolkien would later make major revisions to this lexicon in 1917-1920 while writing The Book of Lost Tales, along with a parallel work, The Gnomish Lexicon.
ANGAMANDU = EREMANDU. or Angamandi (pl.) Hells of Iron Gn. Angband(or)
UTUMNA lower regions of gloom and dark in the North, Melko’s first dwelling. (Gn. UDUM.)
Parma Eldalamberon #12, "The Qenya Lexicon", pages 31 and 99
Angbann(in) "The Hells of Iron". Melko's (Belca's) great fortress, after the battle of countless Lamentation, down to the battle of the Twilight Pool. also in form Ambann(in), Amannin.
uduvna, Udum = Utumna. (Q.) a dwelling of Melko.
Parma Eldalamberon #11, "The Gnomish Lexicon", pages 19 and 74
Likewise in The Book of Lost Tales themselves, both of these places appear, but Tolkien was revising these Tales a lot, often erasing the original drafts when writing revisions, and I don't know if it's possible to determine which of the two ideas was used first.
Angband is referred to a few times in some of the earlier written tales, namely The Fall of Gondolin (where it's not referred to by name, but rather by "Hells of Iron" or "Hells of Melko") and The Tale of Tinúviel (referred to as "Angamandi"). However, while both of these tales were written earlier, the original versions were erased and all we have to go on are later revisions that Tolkien made, after writing many of the other tales.
Utumno doesn't play a role until some of the later written tales (as "Utumna"), namely "The Coming of the Valar", "The Chaining of Melko", and "The Tale of the Sun and Moon" (where it's first explicitly shown to be a distinct dwelling-place from Angband/Angamandi).
If one of them came first I would lean to it being Angband, but the evidence is inconclusive, and they may very well have been conceived at the same time.