When were Gentiles under Law? In "Protestant" Christian sermons, I very often notice that preachers say "we are no longer under the law but under the grace now". I don't understand the logic of these statements since the Mosaic Law was given to Moses and Jewish people and not to the Gentiles. 

With this in mind, I ask in what manner gentiles were under the law and are now under grace?
Here is an excerpt from the writings of Martin Luther, a reformer and founder of Protestantism, that I think that you will agree serves as a prime example of the phenomena that you have observed. In the quote, Luther is discussing two sermons delivered from God, the first at Sinai, where the children of Israel are given the tablets of the Law, and the second at Pentecost in the New Testament, where the Gospel is preached in many tongues by the disciples of Christ. Emphasis is added by me.

Now the first sermon, and doctrine, is the law of God. The second is the gospel. These two sermons are not the same. Therefore we must have a good grasp of the matter in order to know how to differentiate between them. We must know what the law is, and what the gospel is. The law commands and requires us to do certain things. The law is thus directed solely to our behavior and consists in making requirements. For God speaks through the law, saying, “Do this, avoid that, this is what I expect of you.” The gospel, however, does not preach what we are to do or to avoid. It sets up no requirements but reverses the approach of the law, does the very opposite, and says, “This is what God has done for you; he has let his Son be made flesh for you, has let him be put to death for your sake.” So, then, there are two kinds of doctrine and two kinds of works, those of God and those of men. Just as we and God are separated from one another, so also these two doctrines are widely separated from one another. For the gospel teaches exclusively what has been given us by God, and not—as in the case of the law—what we are to do and give to God.

We can interpret Luther's use of the first person plural pronouns &quot;us&quot; to mean we, even all mankind.
Included in the Book of Concord, the doctrinal authority of the Lutheran Church, is the Augsburg Confessions. Article 28 includes this passage:

For it is necessary that the doctrine of Christian liberty be preserved in the churches, namely, that the bondage of the Law is not necessary to justification, as it is written in the Epistle to the Galatians 5:1: Be not entangled again with the yoke of bondage. It is necessary that the chief article of the Gospel be preserved, to wit, that we obtain grace freely by faith in Christ, and not for certain observances or acts of worship devised by men.

It is clear in the doctrinal documents that the Protestants after Luther did not consider the Law to be only applied to Israel, but that it was indeed a pattern of a Supreme Divine Law by which all men are judged, both Jew and Gentile.
Even among the Gentiles, the Jewish people acknowledge that there is a standard of law by which their deeds are measured, which is the Noahide Covenant, since we are all descendants of Noah, though the Jews come from Abraham by Shem and the gentiles from Japheth. In his Demonstration of the Apostolic Preaching, Irenaeus comments on our shared patronage, saying,

Now the blessing of Japheth is on this wise: &quot;God shall enlarge unto
Japheth, and he shall dwell in the house of Shem, and Ham shall be his servant.&quot; That is to say:
In the end of the ages he blossomed forth, at the appearing of the Lord, through the calling of the Gentiles, when God enlarged unto them the calling; and their sound went out into all the earth, and their words to the end of the world. The enlarging, then, is the calling from among the Gentiles,
that is to say, the Church. &quot;And he dwells in the house of Shem&quot;; that is, in the inheritance of the fathers, receiving in Christ Jesus the right of the firstborn. So in the rank in which each was blessed, in that same order through his posterity he received the fruit of the blessing.

Poignantly in his letter to the Church in Galatia cited in the above, Paul says to them,

Galatians 5:14 For the whole Law is fulfilled in one word, in the statement, “You shall love your neighbor as yourself.”

Paul says this after Jesus, who taught us that (Matt 22:36-40),

“You shall love the Lord your God with all your heart, and with all your soul, and with all your mind.’ This is the great and foremost commandment. The second is like it, ‘You shall love your neighbor as yourself.’ On these two commandments depend the whole Law and the Prophets.”

In Romans 2:9-16, Paul confirms that while all men are not responsible to the Law of Moses, they are all responsible to this summary of the Law. Those who do not love God or their neighbor transgress, and those who are righteous according to this, even if they are Gentiles and do not know the Law, still obey the law with their righteousness.

There will be tribulation and distress for every soul of man who does evil, of the Jew first and also of the Greek, but glory and honor and peace to everyone who does good, to the Jew first and also to the Greek. For there is no partiality with God.
For all who have sinned without the Law will also perish without the Law, and all who have sinned under the Law will be judged by the Law; for it is not the hearers of the Law who are just before God, but the doers of the Law will be justified. For when Gentiles who do not have the Law do instinctively the things of the Law, these, not having the Law, are a law to themselves, in that they show the work of the Law written in their hearts, their conscience bearing witness and their thoughts alternately accusing or else defending them, on the day when, according to my gospel, God will judge the secrets of men through Christ Jesus.

And so even without hearing the Law, the one who does the Law is justified, and the one who hears the Law and does not do it is condemned. But can a person who does not know the Law and is wicked be considered righteous because he has not heard it? Of course not. He will parish without the Law just as the wicked man who did have the Law. As a summary of the Protestant position, consider another passage from Romans 3:21-31 as Paul continues,

But now apart from the Law the righteousness of God has been manifested, being witnessed by the Law and the Prophets, even the righteousness of God through faith in Jesus Christ for all those who believe; for there is no distinction [between Jew and Gentile]; for all have sinned and fall short of the glory of God, being justified as a gift by His grace through the redemption which is in Christ Jesus; whom God displayed publicly as a propitiation in His blood through faith. This was to demonstrate His righteousness, because in the forbearance of God He passed over the sins previously committed; for the demonstration, I say, of His righteousness at the present time, so that He would be just and the justifier of the one who has faith in Jesus.
Where then is boasting? It is excluded. By what kind of law? Of works? No, but by a law of faith [that is grace]. For we maintain that a man is justified by faith apart from works of the Law. Or is God the God of Jews only? Is He not the God of Gentiles also? Yes, of Gentiles also, since indeed God who will justify the circumcised by faith and the uncircumcised through faith, is One.

So while both Jew and Gentile alike might have been condemned by God, because righteousness does not come by hearing the Law but by doing the Law and all fall short of doing the Law, God has rescued us from our bondage to condemnation under the law and justified those who were condemned, and justified them through Jesus Christ who believe on him since righteousness does not come by the law, but by faith in Him.