Summary: Annihilating Fire replaces the effect of destruction, but regeneration replaces the destruction itself. Annihilating Fire would not exile.
Replacement effects are not applied in APNAP order; they are applied in the order the affected object's controller or the affected player decides [CR 616.1]. But that doesn't matter here.
The effect of the state-based action being replaced is as follows [CR 704.5g]:
that creature has been dealt lethal damage and is destroyed.
which is to say [CR 701.6a]
that creature has been dealt lethal damage and is destroyed [move it from the battlefield to its owner’s graveyard].
Say Annihilating Fire replacement effect is applied first:
that creature has been dealt lethal damage and is destroyed [exile it from the battlefield].
Regeneration doesn't replace death, it replaces destruction [CR 614.8], so we get:
that creature has been dealt lethal damage, has all damage marked on it removed, and is tapped. If it’s an attacking or blocking creature, remove it from combat.
We get the same result by applying the effects in the opposite order.