There are a number of passages that suggest that Paul preached the same message as the first eleven apostles.
Paul says so:
I went up because of a revelation and set before [the Jerusalem church] (though privately before those who seemed influential) the gospel that I proclaim among the Gentiles, in order to make sure I was not running or had not run in vain.—Galatians 2:2 (ESV)
Luke implies that the Jerusalem church approved of Paul's message:
Then it seemed good to the apostles and the elders, with the whole church, to choose men from among them and send them to Antioch with Paul and Barnabas. —Acts 15:22a (ESV)
And later:
On the following day Paul went in with us to James, and all the elders were present. After greeting them, he related one by one the things that God had done among the Gentiles through his ministry. And when they heard it, they glorified God.—Acts 21:18-20a (ESV)
The author of 2nd Peter put Paul's letters under the banner of Scripture:
And count the patience of our Lord as salvation, just as our beloved brother Paul also wrote to you according to the wisdom given him, as he does in all his letters when he speaks in them of these matters. There are some things in them that are hard to understand, which the ignorant and unstable twist to their own destruction, as they do the other Scriptures.—2nd Peter 3:15-16 (ESV)
According to Paul, he got the gospel directly from God by revelation:
But when he who had set me apart before I was born, and who called me by his grace, was pleased to reveal his Son to me, in order that I might preach him among the Gentiles, I did not immediately consult with anyone; nor did I go up to Jerusalem to those who were apostles before me, but I went away into Arabia, and returned again to Damascus.—Galatians 1:15-17 (ESV)
Acts 9, 22 and 26 detail Paul's conversion and show us that he spoke directly to the resurrected Jesus. We read in various places (e.g., Acts 13:4-12) that Paul was filled with the Holy Spirit. And, of course, he did spend time with the Jerusalem church, Peter and the other apostles. Perhaps Barnabas, John Mark, Silas, and others traveled with Paul was so that they bare witness to the events of Jesus' earthly ministry and repeat His teachings.
As to why Jesus didn't preach more about the Gospel of Grace, I think that stems from a greater mystery: for some reason God wants us to be part of His grand story. God was surprisingly "hands-off" in the Old Testament period. Sure, He brought down fire on wicked cities and rescued His people miraculously on occasion. But for the most part, God expected His people to be faithful and remember His provision for them without intervention.
In the same way, Jesus did surprisingly little to establish His Kingdom while on earth. And the bulk of the church's work to reach the gentile world fell on their shoulders only after He ascended to heaven. Jesus spoke the language of the Jewish peasant, fisherman, merchant, rabbi, and priest, but He didn't have much to say to gentiles. Paul was the right man at the right time for the job of translating that message into a philosophical framework that a Greek-educated person would understand. His struggle for the church was primarily in helping the gentiles see why a provincial Jew's teaching mattered to them.