Regarding Nicca and Anicca natures of Avidya and Prajna

It is the unique & special quality of being "human" (having self-reflective consciousness) that can end ignorance. For example, animals, which operate largely on craving based biological programming, cannot end ignorance.

Ignorance can be ended because craving brings suffering. When it is seen clearly with wisdom craving brings suffering; ignorance can end when the food ('ahara') sustaining ignorance, namely craving (the five hindrances), ceases to arise; allowing samadhi & vipassana to develop. Please refer to AN 10.61 below, which is the relevant sutta for this topic:

Bhikkhus, this is said: ‘A first point of ignorance, bhikkhus, is not seen such that before this there was no ignorance and afterward it came into being.’ Still, ignorance is seen to have a specific condition.

I say, bhikkhus, that ignorance has a nutriment ('ahara'); it is not without nutriment. And what is the nutriment for ignorance? It should be said: the five hindrances.

AN 10.61

But most people delight in craving (as Buddha said in MN 26), including buddhists that crave for reincarnation. In other words, it is a very rare event that the cycle of ignorance and craving end. AN 5.143 says:

Licchavis, the appearance of five treasures is rare in the world. What five? The appearance of a Realized One, a perfected one, a fully awakened Buddha. A person who explains the teaching and training proclaimed by a Realized One. A person who understands the teaching and training proclaimed by a Realized One. A person who practices in line with the teaching. A person who is grateful and thankful.

AN 5.143

As for Nibbana, it does not require wisdom to exist for it (Nibbana) to exist as an element in nature. If Nibbana required wisdom to exist, Nibbana would be conditioned rather than unconditioned. Wisdom is only required to end craving; to allow Nibbana to be known & experienced by a rare human mind. When an enlightened mind ends with the termination of life; the Nibbana Dhatu (Element) will continue to exist.

Nibbana is nicca but wisdom is not nicca. Before the Buddha arose, there was no real wisdom however Nibbana was waiting there to be discovered.

How can something with no beginning (cycle of dependent origination) have an end (Nirodha)?

The above question is unnecessary and based on wrong premises. The Buddha did not teach ignorance has no beginning; that it has existed forever. The Buddha merely said a 1st starting point of ignorance is not known. To quote:

Bhikkhus, this is said: ‘A first point of ignorance, bhikkhus, is not seen such that before this there was no ignorance and afterward it came into being.’ Still, ignorance is seen to have a specific condition.

AN 10.61

And likewise how can a state with no end (Nirvana) have a beginning (Nirodha)?

The above question is a sort of non-sense because it not relevant.

Are Avidya and Nirvana therefore Nicca (Permanent and Unconditioned) or Anicca (Impermanent and Conditioned)?

Nirvana is unconditioned & permanent. Ignorance is conditioned & impermanent. AN 10.61 quoted above says ignorance is conditioned. It must be noted, for most people, including Buddhists who believe in reincarnation, ignorance operates permanently during their lifetime. However, because ignorance can be ended, it is not a permanent element (dhatu).

Put another away, if Prajna is Nicca, how could it give way to the origination and sustenance of Avidya in the first place?

Wisdom is conditioned & impermanent. However, for an Arahant, their wisdom is permanent for their lifetime (MN 12) but because their life is impermanent their wisdom is ultimately impermanent.

If Prajna is Anicca and has a beginning

Yes, wisdom is ultimately impermanent & has a beginning, such as when a mind that has taken refuge in the True Teachings attains stream-entry; which is the beginning of wisdom. Again, the fact is explained in AN 10.61, as follows:

And what is the nutriment for hearing the True Teaching? It should be said: associating with good persons.

AN 10.61

Fortunately, on Buddhist Stack Exchange, there is at least one good person explaining the True Teachings (which accord with non-craving & emptiness).

how can we say that Nirvana (which requires Prajna) is Nicca?

Nirvana already exists but wisdom is required to end the defilements; so Nirvana can be experienced. Wisdom does not "create" Nirvana. Wisdom only removes the defilements that are clouding/covering the peace of Nirvana.

Imagine the blue sky is Nirvana. Wisdom does not create the blue sky. All wisdom does is remove the clouds blocking the view of the blue sky.

If Tanha(craving) is caused by Avijja(ignorance) and if Avijja is sustained by Tanha, the cycle cannot be broken using Avijja and Tanha. But that doesn't mean it cannot be broken using something that is not a link of the Paticca-samuppada(Dependant Origination). Panna(wisdom) or within this context Vijja(non-ignorance) is the opposite of Avijja. It takes out the root cause of Tanha. This breaks the perpetual cycle.

how can a state with no end (Nirvana) have a beginning (Nirodha)?

Nirodha is not a beginning. Nirodha refers to end of all suffering. That is achieved by cutting off the cause of suffering: Tanha(craving). Tanha is cut off by non-ignorance(Vijja). The word Nibbana(Nirvana) refers to the unconditioned Dhamma(reality). It is uncaused and unborn. Hence it has no beginning or end.

Are Avidya and Nirvana therefore Nicca or Anicca?

Avijja here refers to not knowing the four noble truths, not seeing impermanence, suffering and non-self. Avijja is not a thing to be permanent or impermanent. It only points to the lack of Paññā(Wisdom). Nevertheless, Moha(delusion) as a Cetasika(mental concomitant) is caused and it dies when the accompanying thought dies. Therefore it's Anicca(impermanent).

Nibbana is Nicca(permanent).

if Prajna is Nicca, how could it give way to the origination and sustenance of Avidya in the first place?

Paññā is not Nicca(permanent). Paññā has to be cultivated. It belongs to the Sankhara(mental formations/activity) aggregate of the Pancakhanda(Five Aggregates).

If Prajna is Anicca and has a beginning, then how can we say that Nirvana (which requires Prajna) is Nicca?

Nibbana is not dependant on anything. As mentioned above, it is unborn and uncaused. Paññā(wisdom) is required to cut off the defilements that prevent one from seeing Nibbana.