My GreatGrandfather listed in his US census that he was born in Prussia around 1840. I believe that I traced him to Lubeck.
How can I find birth/baptism records for Lubeck/Travemunde for about that time?
If he was Protestan/Lutherian you could try https://www.archion.de/en/
It is an online archive of the german protestant churches, where you can find a lot (albeit not all) church records.
In general, a good starting point is often the FamilySearch Research Wiki page for the place you are interested in.
In the case of Lübeck, the FamilySearch Research Wiki page for civil registration shows that indexes and images for births are available for the period 1811 - 1875, which covers your period of interest.
The page for church records shows that there is a list of parishes available (as the article notes, the main article is in German, but the chart on page 2 of the linked pdf shows the existing parish registers.
If your ancestor was still in Lübeck in 1857, it is worth noting that there was a census in that year, which might have recorded your ancestor and members of his immediate family.