Apparently horse powered ferries were quite common in the early 19th century. At first they used treadwheels, but when treadmills were adapted to horses in the late 1820s this form of transportation really took off. It's said horse ferrys were used in New York until 1920. The treadmill was also adopted to threshers, saws, and pumps. Notably these came about during and not withstanding the Age of Steam due to their simplicity and economy.
It seems the technology should be doable centuries earlier. Paddle wheel ships were known to the Romans and Chinese. There were some very sophisticated machines illustrated by Al-Jazari for instance which featured mechanical concepts like double action pumps, cams, crankshafts, etc that were not re-invented until the 19th century. All of these used the treadwheel, but this had the disadvantage of making horses dizzy and the machinery taking up too much room. Combine these early machines with the horse powered treadmill and it should be very interesting.