The "devil" is one of two places in old wooden ships. Caulkers used to refer to the seam running between the outboard waterways of a ship and the upper deck planking as "the devil". It was a particularly difficult seam to reach and getting a caulking iron into the seam was extremely difficult. Because the caulker was separated by only the thickness of the ship's hull and the ocean, the term "between the devil and the deep-blue sea" came to be used to describe the precarious perch the caulker had to assume to complete the task. If a sailor slipped he could find himself with no ship under his feet as he went over the side, or "between the devil and the deep-blue sea".
Another use of the word "devil" also referred to the seam between the garboard strake and the keel. This seam was usually caulked when the ship was careened for bottom cleaning and maintenance. It was always wet, difficult to reach and extremely awkward to caulk. Although it is one of two definitions, it is also the one which saw more universal use.
To "pay" in nautical terms is to apply something. To "pay a seam" is to push oakum into a seam using a caulking iron and a mallet. Thus the term, "The devil to pay", came to mean any particularly difficult task since "paying the devil" was one of the least desirable jobs in the ship.
There is a bit of myth surrounding the devil. It has been said that when a defaulter was to be keel-hauled he would be "caught between the devil and the deep-blue sea". While that fits, there is little to support its common usage. Keel-hauling, invented by the Dutch, was not a popular form of punishment and most navies had eliminated it by the beginning of the 18th Century in favour of the much more effective "cat-o-nine-tails".
Trivia: We have all heard the term "bitter end". So, where does it come from and why is it bitter?