The word "Paradise" has an intriguing etymology. It is generally thought to have a Persian origin--it is used by various authors to refer to an enclosed garden. This origin can be seen in words like the Latin paries, the Spanish pared, and the Portuguese parede, all referring to walls.
This word entered the Biblical vocabulary through the Septuagint, where it refers to a garden/enclosed area (e.g. Nehemiah 2:8) and, most importantly, the Garden of Eden. The association of this word with the Garden of Eden gave us the modern sense of paradise or paradisiacal being a wonderful or unspoiled place.
See discussion by Thayer here. There's also an extensive discussion of the word in the History of English podcast.
Relationship of Paul & Luke
I did a deeper dive on the relationship of Luke & Paul is this post; by way of quick summary I'll quote Irenaeus of Lyons:
Luke also, the companion of Paul, recorded in a book the Gospel
preached by him (Against Heresies 3.1.1)
This bit of history is multiply attested and uncontested in the early Christian historians--Luke wrote under the apostolic authority of Paul. In fact, the only mentions of Luke by name in the New Testament come from Paul's letters. Without getting too far into the weeds of how the Gospel of Luke relates to the preaching of Paul, suffice it to say that these men were well-acquainted and worked closely together in the ministry.
As such, it should be unsurprising when we find both of them using similar themes, vocabulary, or style (e.g. compare Paul's description of the Lord's supper in 1 Cor. 11 with Luke's description in Luke 22--there is clearly a strong overlap in ideas, one may well be paraphrasing the other).
On this basis, I suggest that when Paul & Luke both use an uncommon word, there is likely to be a correspondence in meaning.
Paul is redundant?
Do verse 2 and verses 3-4 in the OP describe the same realm? I recognize that some believe they do, but in opposition to that view I suggest that if so, verse 3 is quite redundant. What purpose does the repetition in verse 3 serve if verses 2 & 4 are the same story?
The "kai" (and) in verse 3 further reinforces the view that Paul is describing two distinct events/visions/places. Paul's quite capable of using οὐρανός ("ouranos") to refer to heaven, and indeed this is how Luke uses the term--οὐρανός is the place where the Father dwells (see Luke 11:2). The introduction of the distinct word παράδεισος ("paradeisos"/"paradise") in verse 4 suggests he's talking about another place--these are two different visions.
Does Luke contradict John?
As noted in the OP, Luke 23:43 & John 20:17 appear at first glance to conflict with one another. Luke says Jesus will be in paradise today (it's Friday); John says Jesus hasn't yet ascended to His Father (in heaven) the following Sunday.
The etymology of "paradise" makes sense of this conundrum. "Paradise" can very well be used to describe where God is (this appears to be how it is used in Rev. 2:7), but it need not necessarily mean that at all. Paradise is a far more generic term--it refers to an enclosed or exclusive place. This can be a fair description of Eden, or the Bosom of Abraham, or the presence of God, and more.
In this case, there need be no conflict between Luke & John: Luke describes the intermediate state (as outlined in Luke 16), and John describes returning to the presence of the Father after the intermediate state.
Were Paul & Jesus referring to the same place?
I suggest both are referring to the dwelling of the righteous in Sheol/Hades (aka the Bosom of Abraham), not the presence of the Father. This interpretation is supported by the following:
- There would be no contradiction between Luke & John
- Paul is not wasting space repeating himself (in verse 3) on an expensive scroll--the third heaven & paradise are different realms
- There is no conflict with Luke 16 & 1 Peter 3:18-20,4:6 which (to many) describe an intermediate state prior to the resurrection
- The close associates Paul & Luke would be understanding/using the same word the same way
Other interpretations of these passages exist--I find this interpretation to be the one that requires the fewest assumptions.