Pod + instrumental = under something (denotes location).
Pod + accusative = beneath something (denotes movement).
Does this happen with any other preposition?
With some others. For sure "nad" (above), "za" (behind), "przed" (before, in front of), "w" (in, inside)...that's what I can think of right now.
Isn't ,,stołem'' supposed to be ,,stolem'' because of how you say ,,jabłko na stole" the ł changes to l? Or is this a different case?
/Ł/ becomes /l/ if you add a suffix that contains an /i/.
The locative ending for stół is -ie. /Ł/ and /i/ merge and become /l/. But the instrumental ending is just -em, so nothing changes.