Does their previous karma related with the god they worship?

Karma has nothing to do with the lord we worship. In Gita, lord says that the Movement of Karma is extremely complex (Gahan). Ultimately whomsoever we worship based on our Prakriti(nature), be it demigods or (internal) demons or ghosts (past events); it ultimately goes to the supreme soul only.

...does everyone have a similar story like this in their previous birth?

May be or may not be. But it's not important.

BG 9.25

Those who worship the demigods will take birth among the demigods; those who worship the ancestors go to the ancestors; those who worship ghosts and spirits will take birth among such beings; and those who worship Me will live with Me.

We tend to become what we think or worship or act upon. Unless the worship or Yajna is not towards the supreme soul, we continue to be in the cycle of birth and death.

If so, what about the people born in religions like Buddhism, Christianity etc. Moksha is available in Hinduism but how do these religion followers get moksha? Why aren't they given a chance to get moksha?

Not a single religion has any authority over Moksha. Also remember that Religion is not Dharma.

If a person sees supreme soul or Parama Brahman in Jesus or Buddha and offers complete devotion to them, then ofcourse they achieve Moksha. It's similar to others seeing supreme soul in Krishna or Shiva. Krishna, Shiva, Jesus, Buddha are embodied mediums (Saakar) to easily realize Brahman. Similarly a Muslim genuinely worshipping formless god Nirakar Brahman, finally attains Moksha.

However, if we pray to all these gods with material desires in mind (Rajasic worship) then actually it's just a namesake worship, but ultimately we are praying their demigod or may be even demon forms only. Such people don't attain Moksha.

BG 4.12

Men in this world desire success in fruitive activities, and therefore they worship the demigods. Quickly, of course, men get results from fruitive work in this world.

Example: A person realizing supreme soul in Jesus may get Moksha than a person rather than seeking fruits from Krishna.

Do you see any god specific affiliation in below sloka?

BG 4.23

The work of a man who is unattached to the modes of material nature and who is fully situated in transcendental knowledge merges entirely into transcendence.

Does their previous karma related with the god they worship?

Karma has nothing to do with the lord we worship. In Gita, lord says that the Movement of Karma is extremely complex (Gahan). Ultimately whomsoever we worship based on our Prakriti(nature), be it demigods or (internal) demons or ghosts (past events); it ultimately goes to the supreme soul only.

...does everyone have a similar story like this in their previous birth?

May be or may not be. But it's not important.

BG 9.25

Those who worship the demigods will take birth among the demigods; those who worship the ancestors go to the ancestors; those who worship ghosts and spirits will take birth among such beings; and those who worship Me will live with Me.

We tend to become what we think or worship or act upon. Unless the worship or Yajna is not towards the supreme soul, we continue to be in the cycle of birth and death.

If so, what about the people born in religions like Buddhism, Christianity etc. Moksha is available in Hinduism but how do these religion followers get moksha? Why aren't they given a chance to get moksha?

Not a single religion has any authority over Moksha. Also remember that Religion is not Dharma.

If a person sees supreme soul or Parama Brahman in Jesus or Buddha and offers complete devotion to them, then ofcourse they achieve Moksha. It's similar to others seeing supreme soul in Krishna or Shiva. Krishna, Shiva, Jesus, Buddha are embodied mediums (Saakar) to easily realize Brahman. Similarly a Muslim genuinely worshipping formless god Nirakar Brahman, finally attains Moksha.

However, if we pray to all these gods with material desires in mind (Rajasic worship) then actually it's just a namesake worship, but ultimately we are praying their demigod or may be even demon forms only. Such people don't attain Moksha.

BG 4.12

Men in this world desire success in fruitive activities, and therefore they worship the demigods. Quickly, of course, men get results from fruitive work in this world.

Example: A person realizing supreme soul in Jesus may get Moksha than a person rather than seeking fruits from Krishna.

Do you see any god specific affiliation in below sloka?

BG 4.23

The work of a man who is unattached to the modes of material nature and who is fully situated in transcendental knowledge merges entirely into transcendence.