Religious justifications for slavery are as old as the institution itself. In the 17th century Anglo-American case, there were three main biblical justifications (though both were hotly contested even then). Emphasis on any one justification varied with time and, as your question implies, shifted with changes to the structure of slavery and other available "racial" justifications.

First, and most important for later developments, was the Old Testament's explicit sanction for "bond slaves" in Leviticus, 25. Mosaic law clearly allowed the enslavement of non-Israelite "strangers." Leviticus also includes regulations for treatment of bond slaves and requires their conversion and eventual assimilation into ancient Israelite society. In other words, biblical slavery was not heritable like modern racial slavery. This isn't quite a "racial" argument, because, at the time, lines of inclusion and exclusion tended to be as much about religion as race. (Warning: controversial assertion ahead) Like the ancient Israelites, some early American colonists seem to have believed that conversion to Christianity freed slaves and redeemed them from "social death." Because of this unstable basis, other justifications were needed.

This leads to the second main justification for specifically RACIAL slavery - the so-called Curse of Ham. In Genesis, 9:20-27, just after the flood story, Noah gets drunk and passes out naked in his tent. Ham, Noah's son, sees his father's naked body and mocks him (although biblical exegetes have a number of really far out interpretations here...). In revenge Noah lays a curse on Ham's son, Canaan, saying "a servant of servants shall he be unto his brethren." Some early European explorers used the Curse of Ham to explain Africans' dark skin, and once the trans-Atlantic slave trade was underway, the two factors came together to form a potent biblical explanation/justification for both racial difference AND slavery. (To be fair, there were always English subjects who disagreed with this interpretation - see for example, Morgan Godwyn's "The Negro's and Indian's Advocate" [1681] available through Google Books.)

Finally, and this one is a bit further out there, some (admittedly heterodox) early modern thinkers believed that other "species" of humans existed BEFORE God created Adam and Eve. These theories of "pre-Adamite man" or "polygenesis," while not widely accepted in the 17th century, became increasingly accepted as Enlightenment and 19th century "science" increasingly "proved" that different races were distinct species. You don't often see these later thinkers making explicit claims that Africans were descended from pre-Adamite man, but by the 1830s a more secularized version of polygenesis was an important element of proslavery ideology.

(For more on these questions broadly, see David Brion Davis, The Problem of Slavery in Western Culture and Inhuman Bondage.)

Now for your very interesting question about whether conversions forced slave owners to adopt new justifications for slavery. First off, let's just be clear that, until the 1830s or so, very few slaves actually converted to Christianity, and after the 1660s, every colony/state had laws guaranteeing that conversion would not free slaves. That said, from all the primary sources I've seen, from pamphlets to court records to imperial decrees, there seems to have been a lingering doubt about the legitimacy of enslaving fellow Christians. In a series of English legal cases in the early 1700s, Sir John Holt, Chief Justice of King's Bench, declared that Christian slaves in England would have all the rights of any Christian subject, much like Leviticus said about converted slaves - clearly not a stable basis for plantation slavery. My feeling (and at this point it is JUST a feeling...at least until my book gets published) is that "racial" arguments first emerged clearly in response to these antislavery arguments from Christianity. Some of this is also a shift in the tools available to slaveholders. The Enlightenment put "science" on the table in a new way, allowing proslavery ideologues to make arguments about human difference without resorting directly to biblical text.

In the early 19th century and through to the Civil War, religious justifications for slavery remained potent, particularly the Curse of Ham. Indeed, it was EASIER to make a proslavery argument from the Bible, particularly in an age of biblical literalism, than an antislavery argument. If it was such a big deal, slave owners said, wouldn't Jesus have said something about it? Didn't St. Paul say "servants be obedient to your masters even unto death"? Weren't many early Christians slaves, and didn't they remain so even after their conversion? (See Mark Noll, America's God) All this together, for slave owners, made for a potent religious justification, but notice, not a specifically racial justification.

To be balanced, it is important to note that antislavery thinkers also based their arguments in religious or biblical thought. The Quakers, for example, focused on the Golden Rule and denied that Christians could use violence against others, making slavery very difficult to justify. Famously, many evangelicals in the Second Great Awakening in the US found antislavery principles in Christianity. And, of course, enslaved people themselves fashioned an explicitly antislavery Christianity.

So it turns out you can find a bunch of different, often contradictory messages in the Bible...go figure...

TL;DR - Early proslavery thinkers used the Bible extensively to justify the enslavement of Africans. Slave conversions weren't much of a problem, and it was the emergence of an ANTI-slavery religious argument that forced slave owners to craft more explicitly racial justifications.

To what extent was early slavery justified on religious grounds?

The argument that enslavement served to convert the natives to Christianity was brought forward by Sepúlveda but imo it was one of his weaker arguments.
The core arguments in favor of slavery were about egregious violations of natural law (human sacrifices, cannibalism, ...) that the Spaniards had a moral duty to prevent on the one hand and about Aristotle's concept of natural slavery ("Where then there is such a difference as that between soul and body, or between men and animals (as in the case of those whose business is to use their body, and who can do nothing better), the lower sort are by nature slaves, and it is better for them as for all inferiors that they should be under the rule of a master.", Politics I) on the other hand.

From today's point of view of course both Sepúlveda's view of cannibalistic barbarians and Las Casa's conception of somewhat naive but essentially noble savages were horribly misguided.