I can't agree that paddle steamers should be more significant navally. Have they ever been used that way historically? And are they even capable of ocean travel? If I had my way they'd be strictly civilian and coastal transport only.
OK, so I got interested in the topic...
Paddle steamers capable of travel on the ocean were not militarily significant in the real world, but could have been. They had only a very brief period where they were built, that being the late 1830s and the 1840s, during which time there just happened to be little naval warfare going on. Some saw action in the Crimean War in the 1850s, which is when the first combat between steam ships happened. By 1850 they were eclipsed by those using screw propellers instead of paddle wheels, so they stopped building them around then but they were still in use up into the 1860s as warships. The early steam frigates, and smaller classes, were paddle steamers. The last paddle frigates built by the Royal Navy were the HMS Valorous and her sister ship, the HMS Magicienne, launched in 1849 and 1851 respectively (in between was the HMS Furious in 1850 which was a different design, the construction of the second planned ship of this class was never actually started). The British built about 18 paddle frigates. During the same time period they built somewhere near twice that many sail frigates.
They were built for use in smaller bodies of water until at least the late 1860s, such as in the Black Sea or the Mississippi River.
Civilian use of ocean-going paddle steamers was more extensive. The largest ship, by weight anyway, built in the 1800s was a paddle steamer, the SS Great Eastern. A longer but lighter ship was built in 1899, and one that was both longer and heavier in 1901.
The SS Great Eastern was equipped with both sails and paddle wheels (as about all the early and mid era steam ships were). It was an "iron sailing steam ship designed by Isambard Kingdom Brunel, and built by J. Scott Russell & Co. at Millwall on the River Thames, London. She was by far the largest ship ever built at the time of her 1858 launch, and had the capacity to carry 4,000 passengers from England to Australia without refuelling." [Wikipdia article]. So, given that it could sail from England to Austrailia without refueling I think it is safe to say that some paddle steamers are capable of ocean travel.
It's predecessor, in some sense since it was also designed by Isambard Kingdom Brunel, was the SS Great Western. It was "an oak-hulled paddle-wheel steamship, the first steamship purpose-built for crossing the Atlantic, and the initial unit of the Great Western Steamship Company.[3] She was the largest passenger ship in the world from 1837 to 1839. Designed by Isambard Kingdom Brunel, Great Western proved satisfactory in service and was the model for all successful wooden Atlantic paddle-steamers. [...] Great Western was an iron-strapped, wooden, side-wheel paddle steamer, with four masts to hoist the auxiliary sails. The sails were not just to provide auxiliary propulsion, but also were used in rough seas to keep the ship on an even keel and ensure that both paddle wheels remained in the water, driving the ship in a straight line. The hull was built of oak by traditional methods. She was the largest steamship for one year, until the British and American's British Queen went into service." [also Wikipedia] The oak hull was reinforces with iron bands. From another Wikipedia article: "It took 15 days to cross the Atlantic, as compared with two months by sail-powered ships. Unlike the clippers, steamers offered a consistent speed and the ability to keep to a schedule. The early steamships still had sails as well, though, as engines at this time had very inefficient consumption of fuel. Having sails enabled vessels like the Great Western to take advantage of favourable weather conditions and minimise fuel consumption."
The SS Savannah was the first paddle steamer to cross the Atlantic, in 1819, although it was not a full-time steamship. It only used the paddle wheels in clam weather and to maneuver in and around harbors. The ship was much too small to carry enough fuel to run the engine full time across the Atlantic, especially given the inefficient engines of the time. On the trip at least 2 different countries (Sweden and Russia) offered to buy the ship - considering what happened later,perhaps they should have accepted. It was lost off Long Island only 2 years later, although the steam engine and paddle wheels had been removed and sold the previous year by the new owners, after the ship was sold due the the owning company having financial difficulties following a fire sweeping though part of the city of Savannah where they were located (hence the name of the ship). It was not considered a success, among other things it had never actually run a regular delivery service between the US and Liverpool which was the reason it was built, only ever making that one trip across the ocean.
After the SS Savannah, the US didn't launch any more ocean going steamships for another 30 years (which seems odd to me). The British, and others, launched a bunch of them. Steam powered ships gradually replaced the sailing ships, but never completely until well after the invention of the steam turbine and by that time they were not using paddles since the screw propeller was perfected before 1850 and gradually replaced the paddle wheels.
In 1849 the California Gold Rush began. One way that people got to it from the eastern and southern US was to take steamships to Panama or Nicaragua, cross to the west coast, and then take steamships from Panama to California. One of the earliest oceangoing steamships launched in the US after the SS Savannah, in 1848, just happened to be on its way around South America to California when that started. So many people rushed to Panama to meet her coming up the west coast that it could not take most of them even though it ended up carrying double its rated number of passengers. Although it was mainly used as a coastal vessel, it was capable of ocean travel. The reverse route was how a lot of the gold made it back east - steamship to Panama, overland, and steamship to the east coast.
There is still one ocean-going paddle steamer in service, the PS Waverley. It is operated as a tourist ship for passenger excursions by the Paddle Steamer Preservation Society. It was launched in 1946 after it's predecessor of the same name was sunk while evacuating troops from Dunkirk in WWII.