relative pronoun at the beginning of the sentence

Your assumption is correct, the two uses of whose respectively belong to the "Right Honorable my very good Lord" and "your good Ladyship".

In your quote, the first occurence is used in a rhetorical question ("Whose carriage of causes have purchased you respect of all men[?]"), and the second one in an adjective (or relative) clause ("To your Ladyship they do belong likewise; [your Ladyship,] whose religion and justice do challenge at my hands").
These are both grammatically correct in modern English as well, but the only valid sentence beginning with the word 'whose' is a question.

"To you (Right Honorable my very good Lord) of right do they belong:

[The thing - "They"] belong to you [My Lord - Lord of the Manor] by right. That is: You have rightful ownership of the thing...

for to whom shall I rather present the first fruits of my learning than to your Lordship:

Because you are the rightful owner - who else should I be presenting the benefits [fruits of my labour / learning]?

who nourished then both me and them, when there was scarce any being to me or them?

Because you supported me when I had nothing and while I was learning. Therefore [I feel] this give you the rightful ownership of the benefits of my learning - I give you 'first refusal' to benefit from the fruits of my learning that you have supported...

And whose just and upright carriage of causes, whose zeal to justice and honorable courtesy to all men, have purchased you a reverend and worthy respect of all men in all parts of this kingdom, where you are known.

[just and upright carriage of causes] - Justifiable and honourable actions in supporting me (the good cause)

[whose zeal to justice and honorable courtesy to all men] . Your [The Lordship's] desire to support justice and honourable actions and common courtesy...

And to your good Ladyship they do of great right belong likewise;

This right of ownership also belongs to your wife [Ladyship] - speaking directly to the Lady...

whose religion, justice, and honorable admittance of my unworthy service to your Ladyship do challenge at my hands the uttermost of what ever I may be able to perform."

Who, because of your [her] religious beliefs your belief in justice and your agreement to allow me[admittance - admit - allow in] to do [the thing], this has made anything I am able to do in return 'unworthy' or insufficient to ever repay you.

The writer is saying that, in their opinion, the Lord of the Manor and his wife [Ladyship] have a moral right to also benefit from the 'fruits of [the writer's] learning', that is, the writer wishes to express their gratitude for the Lord & Lady's support, which was the only reason they were able to learn. The writer wishes to give the Lord and Lady the opportunity to gain some [possibly] financial benefit in return.

The writer thinks that the Lord and Lady have this right because, without their support, the writer could not have learned the things that they have.

The writer is also expressing modesty, by saying that what ever they [the writer] do {at my [own] hands or by my actions}, it will never be enough to sufficiently repay the Lord & Lady's generous support.