So when and where did the actual “Paddy lay back...” bit first make its appearance?

“Although really outward bound from Rio, as far as the crew is concerned the “Guarneri” is homeward bound for most of them hail from North Sea ports.

One may be sure that they put real sentiment into the ancient Chanty:

                "PADDY LAY BACK"

It was on a cold and wintry morning in December
That I walked along the streets of Dublin Town,
Where my money had all gone I couldn't remember
An' I hadn't got a friend in all the town
So I signed up on a brig called the “Oxford.”
Bound for Chile an' Peru,
They were a jolly bunch I well remember––
The skipper, mates, the cook an' all the crew.
                Chorus:
“Oh, Paddy, lay back,
Pull in your slack,
All hands round the capstan,
Heave up all!
'Tis a cold and wintry morning in December
An' we're bound for the West Coast––
Round the Horn.”

        The Chantyman's job is an important one and he is generally a big-chested, leather-lunged and weather-tanned descendent of the long dead tribe of King's Jesters for the Chantyman must be able to improvise at a moment's notice proper stanzas in accordance with passing events aboard the ship. He is of a humorous turn of mind, and by a witty stanza or two manages to keep the crew in a happy frame of mind even at the most discouraging moments.”
[D'Oliveira, L.V. LeCocq, White Wings, Brazilian American, vol.12, no.295, 20 June 1925]

Also:
On the Banks of the Sacramento
Blow the Man Down
Robin Ranso
Yarra River
Bound for Baltimore