For its part, the OED attributes all these compounds to variations of play-off, which in sports held this early meaning cited in 1895:
A match or rematch played to decide a draw or tie.
However, in attributing these variations like "bake-off" and "cook-off" to "play-off," the OED is opting not to attribute the phrases to the earlier terms cited in Edwin Ashworth's answer, face-off which held an earlier meaning in hockey, and stand-off, which first meant a tie in a game of cards, which might not fall into the same realm of meaning as "bake-off" or "cook-off" or "play-off," but certainly seems related.
Thus, if a man bets on the ace and deuce, and the ace comes to his side, and the deuce to the dealer's side, it is a stand-off, and neither wins.
- 1843 J. H. Green Exposure Arts & Miseries Gambling 187
Ultimately, I find the OED's conclusion most satisfactory, as a "bake-off" or "dance-off" are, in essence, tournament-style competitions similar to a "play-off."
As a transitive verb, "play-off" is cited earlier than as a noun, in 1870:
On the tie being played off, Sir Robert and Mr. Anderson again tied.
- 1870 C. MacArthur Golfer's Ann. 118
Only later, first cited in 1932, did "play-off" come to mean:
(Each of) a series of games, matches, or contests played to decide a championship, competition, etc.; (also) a preliminary series of matches to decide which individuals or teams qualify for a championship or competition.
As in this citation:
The play-off for the Middle Atlantic League baseball title will start Wednesday.
- 1932 Sun (Baltimore) 6 Sept. 14/2
And it wasn't long until people were doing more than just "playing" off.
There will be a grand cook-off with five sectional winners competing.
- 1936 Port Arthur (Texas) News 3 May d4/3
Although this hardly impacts the conclusion of this answer, "cook-off" can be antedated beyond the OED's citations. This 1931 newspaper clipping describes a "Cooking Contest" as a "cook off."
