Paradise was that part of Sheol, the grave, the realm of the dead where the righteous were held separate and apart from the place of torment where the unrighteous were held waiting for the resurrection which Jesus prophesied would happen after He destroyed the temple in Jerusalem (Matt. 24-25).
Paradise was not heaven, but was part of the "prison" of Hades which Jesus held the keys to (Rev. 1:18). As He told the thief that he would be with Christ in Paradise that same day, and as Christ was in the grave for three days and three nights, then Paradise was that part of the grave where Christ was. The rabbis called it Abraham's Bosom. Luke 16:23-31 provides the picture of that realm of the dead.
As Jesus was resurrected on the 3rd day (Matt. 17:23), and as the grave could not hold Him (Acts 2:24), then He did not remain in Paradise. When He ascended to the right hand of the Father (Acts 1:9), He was in heaven with the Father. Paradise was not in heaven.
As Christ told His disciples that He would separate out all of those from the grave, the sheep (righteous) to His right and the goats (unrighteous) to His left when He returned to destroy that temple, which He did in AD 70, then that grave, or realm of the dead has been taken away. Revelation 20 said it was thrown into the lake of fire.
Christ said that the prison of Hades would not prevail against His church. It no longer exists, and no longer holds any of those who belong to Christ. The process of judgment at our bodily death has always been the same.
"and as it is laid up to men once to die, and after this -- judgment," (Heb. 9:27, YLT)
We are judged when we die. That is why Lazarus was placed in Abraham's Bosom, and the rich man was placed in torment in Tartarus. But, the place of the dead has changed. Rev. 14:13 provides that clue.
"And I heard a voice out of the heaven saying to me, Write: Happy are the dead who in the Lord are dying **from this time**!' Yes, (saith the Spirit,) That they may rest from their labours -- and their works do follow them!'" (YLT)
After the destruction of Jerusalem, after Christ took all those out of the grave and took the righteous home to heaven, all those who have died in the Lord since that judgment day have been resurrected, changed in the twinkling of an eye (1 Cor. 15:52) and gathered home to heaven to be with all of those who have gone before. That is now the process.
See "Hades Is No More" here: ShreddingTheVeil. See also "The Signs of Revelation - Part VI: Judgment Day here: here, and "Testing The Spirits - Part III: Daniel's Lot" here: here.