marine (n.)youdaoicibaDictYouDict
14c., "seacoast;" see marine (adj.). Meaning "collective shipping of a country" is from 1660s. Meaning "soldier who serves on a ship" is from 1670s, a separate borrowing from French marine, from the French adjective. Phrase tell that to the marines (1806) originally was the first half of a retort expressing skepticism:
"Upon my soul, sir," answered the lieutenant, "when I thought she scorned my passion, I wept like a child."

"Belay there!" cried the captain; "you may tell that to the marines, but I'll be d----d if the sailors will believe it." ["John Moore," "The Post-Captain; or, the Wooden Walls Well Manned," 1805]
The book, a rollicking sea romance/adventure novel, was popular in its day and the remark is a recurring punch line in it (repeated at least four times). It was written by naval veteran John Davis (1774-1854) but published under the name John Moore. Walsh records that, "The marines are among the 'jolly' jack-tars a proverbially gullible lot, capable of swallowing any yarn, in size varying from a yawl-boat to a full-rigged frigate."
punch (n.3)youdaoicibaDictYouDict
"a quick blow with the fist," by 1570s, probably from punch (v.). In early use also of blows with the foot or jabs with a staff or club. Originally especially of blows that sink in to some degree ("... whom he unmercifully bruises and batters from head to foot: here a slap in the chaps, there a black eye, now a punch in the stomach, and then a kick on the breech," "Monthly Review," 1763). Figurative sense of "forceful, vigorous quality" is recorded from 1911. To beat (someone) to the punch in the figurative sense is from 1915, a metaphor from boxing (attested by 1913). Punch line (also punch-line) is from 1915 (originally in popular-song writing); punch-drunk is from 1915 (alternative form slug-nutty is from 1933).