In the Middle Ages, it was not uncommon for kings and other nobles to have extra-marital affairs. Sometimes such affairs were semi-public. Even a few Popes (such as Alexander VI) had girlfriends during their papacy. Why did the Catholic church turn a blind eye to this? How did the Kings and Popes justify their behavior?
Provided one steers clear of heresy by not challenging the tenets or dogmas of the faith (see for example Nicene Creed, Arianism, Walk to Canossa, and Galileo), the Church is in the forgiveness business rather than the condemnation business.
This business became so profitable for the Church that it began the practice of selling indulgences to faithful adherents:
Indulgence: a remission before God of the temporal punishment due to sins whose guilt has already been forgiven, which the faithful Christian who is duly disposed gains under certain prescribed conditions through the action of the Church which, as the minister of redemption, dispenses and applies with authority the treasury of the satisfactions of Christ and all of the saints.
So there was never any need to justify one's sins, to anyone. One simply confessed, atoned, and received absolution.
The Church has never been a monolith speaking with one voice, and at all times some parts of the Church condemned adultery in high places as well as in low ones.
Why did some parts sometimes stay silent?
If it's your king who's the adulterer, it can be unsafe to be too outspoken. Henry VIII was a pious man, but criticizing his marriage decisions could be a quick route to martyrdom. Some chose just that. Many others, being fallible humans, played it safe. "Nothing to see here! Nope, nothing. (walks off whistling...)"
There were bigger fish to fry. Few people today understand in their bones just how dangerous things were in the past. (Go watch Game of Thrones. It's not that far off.) Many people -- good, moral, intelligent, well-meaning people -- looked at a bit of adultery as a price to be paid for a stable society. Would you re-start the Wars of the Roses to make a point about adultery?
The Renaissance was one of the times when Italian politics allowed various powerful Italian families capture the Papacy. (Another was a period in the first millennium called by one historian "The Iron Years of the Papacy" when the office was captured by local Roman noble families and traded between them.) Both times the Popes were denounced by churchmen all over Europe (safely outside of the reach of the Borgias and the other m/a/f/i/a/ important families). Even within Italy it those Popes were criticized by brave souls...and also by all the churchmen in towns controlled by the Pope's enemies.
Finally, it's important to distinguish between adultery and unmarried sex. Adultery was religiously the graver sin and politically MUCH more dangerous since it messed up inheritance, and a messed up inheritance had a big chance of turning into violence. The great reforms around the year 1000 established that church offices (which had often been controlled by local aristocracy during the period 500-1000 AD) were not hereditary. A necessary part of the reform was that priests could not marry, since it was widely accepted that bastards could not inherit. (This is not a religious limitation. Eastern Orthodox priests marry to this day. And married Anglican priests remained both married and priests if they convert to Catholicism.) Consequently, Papal bastards lacked the same societal impact of royal bastards, and the objections to them were only religious, thus muting them somewhat.
(And as far as the part of question "Hod did they justify their behavior?" goes, the justification was "I'm king and I want to do it." (As far as the Renaissance Popes go, they said much the same thing, but in Latin.)
The short answers is: extramarital affairs (or, as another answer puts it: sins in general) are not meant to be "justified". Especially kings didn't need to justify such sexual relations. Far for being exceptional they were taken for granted. - The term "affair" is already misleading. The situation was different for men and women, and different for nobles and commoners. (The sexual relation of a nobleman with a woman commoner wouldn't have even been noticed, and would hardly qualify as an "affair".)
The OP seems to imagine the Middle Ages as a world of church repression against the individuals which only the more powerful ones could resist. That image is too simplistic and not very true, for various reasons:
The Catholic Church had other priorities and truly other "vocation" in the Middle Ages .
Medieval Catholic sexual habits were more free than those of the more recent post-Reformation, puritan and "bourgeois" era.
Commoners, especial in rural areas were not representing a sufficiently important object of interest and control.
The aristocracy had the real power; the Church had to adapt to its habits and morals. Most importantly, the Church was made mostly of aristocrats that entered the church as a career not as a fanatical and puritanical vocation.
"Adultery" meant different things depending on the society, the moment, other contextual aspects.
Men enjoyed a much larger sexual freedom than women.
Pre-marital sexual freedom was much more repressed than the post-marital one, and that almost exclusively for women. In some contexts "virginity" was very important; but it was anyway more important than "fidelity". Unsurprisingly, fathers and husbands were much more interested in limiting adultery than the church was.
When virginity was important, the possibility of sexual freedom of women increased in fact after marriage.
Repression in sexual matters involved reasons of (mostly masculine and aristocratic) prestige - hence the importance of virginity. Fidelity was important only as far as it reinforced this prestige. Considering the prestige of kings, princes and other great aristocrats, their extramarital affairs were not necessarily a diminishing factor.
Marriages were not usually meant to be based on love in the upper classes, but on economic and dynastic reasons. (Even against the church's position that the spouses' decision was sufficient to a lawful marriage, parents' approval was usually mandatory in practice and even by law, like in France). An imposed loveless marriage was not only a probable cause for adultery, but also for tolerance as far as adultery was concerned.
Sexuality in general is much more a post-Reformation and modern obsession than a medieval one. The sexually obsessed and repressed "medieval" church is more a 19th century fantasy (and reality) of the Victorian society than a 13th century one.
In some special cases, a special form of "adultery" was encouraged by the medieval culture - namely, in the tradition of the courtly love, in which various degrees of chastity were involved.
Adultery in the sense of unlawful sexual relations between married people was as much condemned as it was widespread and tolerated, and when it was most effectively repressed it was not because of the church, but because of the tight control of the community over the individuals. A small village where everybody knows everybody was probably a much more "repressive" environment for unlawful relations than it was a city or an aristocratic court. On the other hand, one has just to take a look at the realist paintings of the Flemish school depicting village feasts; just like the aristocratic morals,the rural ones were more free than what was later called "bourgeois" mentality, which was mainly a creation of the post-Reformation era.
As the Middle Ages are precisely the period when a harmony between Christianity and the (formerly pagan barbarous invaders, mostly of German origin) warmongering aristocracy was achieved, the church (that is the Catholic church) became part of an aristocratic society that it fully permeated, but that also permeated the church.
The main interests of the Church in changing the society involved much more faith (fight against heresy, the following of the liturgical rites) and politics (limiting war between Christians, expanding the power of the papacy, fighting the non-believers) than individual morals.
The private aspects of life became more religiously important after the Middle Ages, because of different factors that are inter-connected: the development of the individualist religiosity, the Reformation, de development of the modern state and society with a larger scope of intervention in the private life of the people.
Adultery and other "vices" were not only condemned, but very present and at the same time considered "normal": man was considered sinful by definition and sin was expected to happen. Church was expected to intervene in this context and at this point. Its most important action was not preventive or hygienistic, as sin was considered to be already there in any case; as mentioned in the other answers, confession and atonement were very important - in fact more important than interdiction and repression.
Aristocrats equaled being noble to being free and they have only reluctantly abandoned this liberty along the centuries. The first liberty that they had to partially renounce was their right and inclination to wage war. That was one of the main initial problems of the relation between church and society at the beginning of the medieval era, and the ideal of the peace and truce of God may be considered one of the fundamentals of the medieval society. (That level of church intervention on aristocratic morals was never equaled by any other subject, including sexuality.)
The second great limitation to the aristocratic power came not from the church but from the centralized monarchical state between the 14th and the 17th centuries; the degree to which aristocratic independence from the king was preserved varied in Europe (it remained greater in England and Spain than in France, even greater in Poland or Italy), but state order became more and more present everywhere, with the lower classes, namely the merchants of urban centers, as the most zealous servants of the king's administration and authority. This developments go beyond the strict limit of the medieval era but are significant for the logic that ruled the aristocratic morality. As a reaction to their declining power in politics and army, aristocrats developed an even more particularist and exceptionalist morality that included sexuality and marked them as being above the commoners. That has evolved in later times into an "elitist" culture that in parts of Europe has permeated and influenced the lower classes of society and has given an "aristocratic" twist to the habits of a whole country, including its sexual norms (Italy, Spain, and especially France; in other parts of Europe the culture of the newly enfranchised classes went against this; in England, for example, this trend of adopting the habits of higher society was stigmatized as snobbery; Prussia, where the aristocracy has succeeded in reserving military prestige for itself, while imposing it to the whole society for imitation, is a rather special case.)
To take a glimpse of what morals in the medieval Europe were, one has to look at Chaucer's Canterbury Tales or Boccaccio's Decameron. Far from being strictly "Renaissance-styled" in the sense of non-medieval, it is an image that the Renaissance shared much more with the previous centuries than with the future ones. Far from being a medieval mark, the religious grip on individual sexuality - and especially on that of the commoners - tightened in fact with the Reformation, the counter-Reformation, and the rise of the bourgeoisie and of the modern state.
As far as sexuality and morality are concerned, the medieval catholic man of the 10th-13th centuries was probably more ignorant but far less hypocritical than the protestant and catholic of the 17th-19th century. And I fear that the image that many people have on both the middle ages and the catholic countries is biased by a more recent sensibility for which even Shakespeare appeared immoral.
For starters, there is nothing specifically Roman Catholic about the behavior in question, since it was well-spread in Eastern Orthodox lands as well, where divorce and remarriage, though restricted, are not completely forbidden.
Secondly, to answer a question with another question : If medieval Slavs and Romanians were Christians, why did they practice the (pagan) custom of unburying some of their dead, suspected of vampirism (hardly a Christian concept), carving out their hearts, burning them, mixing the ashes with water, and then drinking the solution ?
The answer is very simple : In the past, as today, Christianity was not the only influence on society. Many pre-Christian traditions were kept alongside the newly-adopted faith for centuries, and some exist and are practiced until this very day, especially within traditional rural communities.
Furthermore, given the fact that the Old Covenant is ripe with polygamy, especially as it pertains to the various God-fearing Jewish kings, the issue of God-fearing Christian kings keeping mistresses at the royal court was most likely among the least suspicious of all not-particularly-Christian habits practiced by our ancient ancestors in the distant past.