The following year he volunteered to serve under John "Roaring Jack" Percival in the Dolphin as that vessel pursued mutineers of the whaler Globe, then returned to United States.

Appointed to command the sloop-of-war Levant in 1838, he made a cruise in the West Indies and in 1841 became Executive Officer of the New York Navy Yard.

The squadron was instrumental in foiling the expedition against Nicaragua underway by the American William Walker, who had dreamed of uniting the nations of Central America into a vast military empire led by himself.

After his surrender to an allied Central American army and his return to the United States, Walker attempted for a military comeback when he was captured in 1857 by a landing of Home Squadron Marines.

Stateside controversy over the questionable legality of seizing American nationals in foreign, neutral lands prompted President James Buchanan to relieve Paulding of his command, forcing him into retirement.

Paulding was assigned to evacuate ships from the Norfolk Naval Shipyard, which the Confederates planned to seize, in April 1861.