As mentioned in the comments Lord Vishnu does not have only ten incarnations. There are many more mentioned in various scriptures. Shrimad Bhagvat Puran mentions 22 incarnations of Lord Vishnu and am sharing the list:
- Four Kumaras – children who live as yogis
- Varaha - non-human (boar)
- Narad - a Devarishi
- Nara-Narayan – twin-rishis who were born to Dharma & Murti
- Kapil – another rishi
- Dattatreya – an Avadhut and Yogi
- Yajna – a previous Indra
- Rishabh Dev – a king who turned into the first Jain Tirthankar
- Prithu – the king after whom earth is called Prithvi
- Matsya - non-human (fish)
- Kurma - non-human (turtle)
- Dhanvantari – physician & father of Ayurveda
- Mohini – the only female incarnation
- Narasimha - The man-lion
- Vaman - a brahmin dwarf boy
- Parashurama - another brahmin boy who became a kshatriya killer
- Shri Rama - the 'Perfect King'
- Ved Vyas – rishi who composed puranas, mahabharat and compiled Vedas.
- Balarama - brother to Krishna and a prince
- Krishna - the famous Yadav prince and expounder of Bhagvad Geeta
- Buddha - a prince who became a yogi
- Kalki - The future avatar
As you can see from the above list Nara and Narayan are definitely the incarnations of Lord Vishnu. Regarding their time period, it is definitely not the current Mahayuga since the above avatar list is in chronological order and you see a huge gap between Nar-Narayan and Krishna who was born in the Dwapar of the current Chatur-yuga period. In fact even the Treta Yug bit may not be correct since this is what Section CCCXXXV of the Shanti Parva of Mahabharat mentions:
O slayer of foes, expound it to thee! In this connection is cited the old history of the discourse between Narada and the Rishi Narayana. I heard it from my sire that in the Krita age, O monarch, during the epoch of the Self-born Manu, the eternal Narayana, the Soul of the universe, took birth as the son of Dharma in a quadruple form, viz., as Nara, Narayana, Hari, and the Self-create Krishna. Amongst them all, Narayana and Nara underwent the severest austerities by repairing to the Himalayan retreat known by the name of Vadari, by riding on their golden cars.
This would imply their advent in perhaps the very first Satyuga of the Swayambhu or the 1st Manvantar. This section actually mentions both Nara & Narayan performing a rigorous tapasya though it doesn't link it to the killing of Dambodbhava:
Those original regents of the world who had taken birth as the sons of Dharma, became exceedingly emaciated in person in consequence of the austerities they had undergone. Indeed, for those austerities and for their energy, the very deities were unable to look at them. Only that deity with whom they were propitiated could behold them.
In fact every parva of the Mahabharat begins with an invocation to Nar and Narayan:
नारायणं नमस्कृत्य नरं चैव नरॊत्तमम
देवीं सरस्वतीं चैव ततॊ जयम
Bowing to Lord Nārāyaṇa, to Nara, the best of men, and to the Goddess Sarasvatī, then may one commence the Jaya.
Coming to the second point, the only reason for Lord Krishna's birth was not the death of Kamsa but of all Asuras on earth. His arrival was to destroy ALL evil kings and tyrants as mentioned in the Yog Vasishth Chapter 22:
Vishnu is yet to be born in his sixteenth incarnation at Vasudeva’s abode for the purpose of rescuing the earth from the burden of the oppression of its tyrant lords and despots.
There were many of those as mentioned in Section LXVII of the Sambhava Parva of Mahabharat. The same section mentions once more Krishna being a rebirth of Narayan & Arjun that of Nara:
Let this Varchas, therefore, go thither, but let him not stay there long. Nara, whose companion is Narayana, will be born as Indra's son and indeed, will be known as Arjuna, the mighty son of Pandu.
And he, called Vasudeva, endued with great valour, was among men a portion of him called Narayana--the god of gods--eternal.
Regarding the other Pandav brothers the same section mentions this about their being sired by the gods:
And, O monarch, learn that king Yudhishthira was a portion of Dharma; that Bhimasena was of the deity of wind; that Arjuna was of Indra, the chief of the celestials; and that Nakula and Sahadeva, the handsomest beings among all creatures, and unrivalled for beauty on earth, were similarly portions of the twin Aswins.
As regards their previous lives, Section CLXLIX of the Vaivahik Parva of Mahabharat mentions them as Indras in the previous birth:
Hearing these words the god of fiery energy smiled and said, 'Those that are of disposition like thine never obtain my grace. These others (within the cave) had at one time been like thee. Enter thou this cave, therefore, and lie there for some time. The fate of you all shall certainly be the same. All of you shall have to take your birth in the world of men, where, having achieved many difficult feats and slaying a large number of men, ye shall again by the merits of your respective deeds, regain the valued region of Indra. Ye shall accomplish all I have said and much more besides, of other kinds of work.'
Then those Indras, of their shorn glory said, 'We shall go from our celestial regions even unto the region of men where salvation is ordained to be difficult of acquisition. But let the gods Dharma, Vayu, Maghavat, and the twin Ashwins beget us upon our would-be mother. Fighting with men by means of both celestial and human weapons, we shall again come back into the region of Indra.'.....And those Indras of old who had been confined in the cave on the Himavat are none else than the sons of Pandu, endued with great energy.
I hope this helps clear your doubts about Nara-Narayan as well as the other Pandava brothers.