The origin of the expression 'move heaven and earth'?

Your question set me thinking because in French we have the exact same expression meaning the same thing, remuer (le) ciel et (la) terre. A quick research led me to Montaigne's Essais. It's the earliest example of the phrase I managed to find. He uses it in a context that is consistent with your intuition, namely that of a change in calendar, more specifically the change from the Julian to the Gregorian calendar that occurred back in 1564 in France.

Here's the quote in French:

  • Il y a deux ou trois ans, qu'on accoursit l'an de dix jours en France. Combien de changemens devoint suyvre ceste reformation ! Ce fut proprement remuer le ciel et la terre à la fois. Ce neantmoins, il n'est rien qui bouge de sa place : Mes voisins trouvent l'heure de leurs semences, de leur recolte, l'opportunité de leurs negoces, les jours nuisibles et propices, au mesme poinct justement, où ils les avoyent assignez de tout temps

Montaigne's Essays were first translated into English by John Florio and published in 1603. Here's the interesting bit (I've modernized Florio's spelling):

  • Two or three years are now past since the year hath been shortened ten days in France. Oh how many changes are like to ensue this reformation! It was a right removing of Heaven and Earth together, yet nothing removeth from its own place: My Neighbours find the season of their seed and Harvest time, the opportunity of their affairs, their lucky and unlucky days, to answer just those seasons to which they had from all ages assigned them.

Here's a later translation by Charles Cotton (1685):

  • ‘Tis now two or three years ago that they made the year ten days shorter in France. How many changes may we expect should follow this reformation! it was really moving heaven and earth at once. Yet nothing for all that stirs from its place, my neighbours still find their seasons of sowing and reaping, the opportunities of doing their business, the hurtful and propitious days, just at the same time where they had, time out of mind, assigned them.

I don't know if to move heaven and earth goes back to the French through Montaigne. Heaven and earth was a set phrase in English before that but in any event the image was certainly easily and readily understood through the Christian culture and mindset that the French and the English were both sharing.