Acording to the Catechism of the Catholic Church (as usual, emphasis is mine):
577 At the beginning of the Sermon on the Mount Jesus issued a solemn warning in which he presented God's law, given on Sinai during the first covenant, in light of the grace of the New Covenant:
Do not think that I have come to abolish the law or the prophets: I have come not to abolish but to fulfill. For truly I tell you, until heaven and earth pass away, not one letter, not one stroke of a letter, will pass from the law, until all is accomplished. Therefore, whoever breaks one of the least of these commandments, and teaches others to do the same, will be called least in the kingdom of heaven; but whoever does them and teaches them will be called great in the kingdom of heaven.
So far, so good: it is as the OP has commented. Jesus himself says that he has come to "fulfill" and not to "abolish" the law.
578 Jesus, Israel's Messiah and therefore the greatest in the kingdom of heaven, was to fulfill the Law by keeping it in its all embracing detail — according to his own words, down to "the least of these commandments". He is in fact the only one who could keep it perfectly. On their own admission the Jews were never able to observe the Law in its entirety without violating the least of its precepts. This is why every year on the Day of Atonement the children of Israel ask God's forgiveness for their transgressions of the Law. The Law indeed makes up one inseparable whole, and St. James recalls, "Whoever keeps the whole law but fails in one point has become guilty of all of it."
Here the Church points out that no one, save the Son of God, was able to keep all of the law, and the Jewish ceremony of Yom Kippur testifies to that. At the same time, the Law is whole and indivisible: there cannot be multiple levels of compliance with the Law.
580 The perfect fulfillment of the Law could be the work of none but the divine legislator, born subject to the Law in the person of the Son. In Jesus, the Law no longer appears engraved on tables of stone but "upon the heart" of the Servant who becomes "a covenant to the people", because he will "faithfully bring forth justice". Jesus fulfills the Law to the point of taking upon himself "the curse of the Law" incurred by those who do not "abide by the things written in the book of the Law, and do them", for his death took place to redeem them "from the transgressions under the first covenant".
Through Jesus's death, the Perfect Sacrifice, the Law is fulfilled, and thus the penalty for failing to uphold the Law is paid by Him. Thereafter, those who believe in Him can point to that Sacrifice as reparation for their transgressions of the Law.
581 The Jewish people and their spiritual leaders viewed Jesus as a rabbi. He often argued within the framework of rabbinical interpretation of the Law. Yet Jesus could not help but offend the teachers of the Law, for he was not content to propose his interpretation alongside theirs but taught the people "as one who had authority, and not as their scribes". In Jesus, the same Word of God that had resounded on Mount Sinai to give the written Law to Moses, made itself heard anew on the Mount of the Beatitudes. Jesus did not abolish the Law but fulfilled it by giving its ultimate interpretation in a divine way: "You have heard that it was said to the men of old. . . But I say to you. . ." With this same divine authority, he disavowed certain human traditions of the Pharisees that were "making void the word of God".
Jesus did not abrogate the Law, but fulfilled it, by going above the conventional Rabbinic interpretations of Scripture, but by teaching them directly. His teachings are fully compatible with Mosaic Law, but are above them as perfectly realised expressions of the will of God.
582 Going even further, Jesus perfects the dietary law, so important in Jewish daily life, by revealing its pedagogical meaning through a divine interpretation: "Whatever goes into a man from outside cannot defile him. . . (Thus he declared all foods clean.). . . What comes out of a man is what defiles a man. For from within, out of the heart of man, come evil thoughts. . ." In presenting with divine authority the definitive interpretation of the Law, Jesus found himself confronted by certain teachers of the Law who did not accept his interpretation of the Law, guaranteed though it was by the divine signs that accompanied it. This was the case especially with the sabbath laws, for he recalls, often with rabbinical arguments, that the sabbath rest is not violated by serving God and neighbor, which his own healings did.
Here, we are reminded of the instances in the Gospels where Jesus seems to invalidate or abrogate Mosaic Law, but instead perfects it, returning it to its original spirit.
And because the observance of the letter of the Law interfered with its spirit, St. Paul reasoned that the Gentiles should not be forced to uphold it. Recall that St. Paul himself observed the precepts of the Law just as much as when he persecuted Christians (cf. Phillipians 3), as he was Hebrew himself, but that the insistence in following Jewish customs might cause Gentiles to deviate from Jesus's teachings to Moses's, which would be putting the cart before the horse (cf. Acts 15).
Thus the Church sees no contradiction in Jesus's position that he fulfilled the Law and Paul's position that following the Law is not necessary for justification in Christ.