Making their New York debut at a branch of the Cafe de Paris , the duo were soon in demand on stage , in vaudeville and in motion pictures . Making their New York debut in 1912 at a branch of the Cafe de Paris , operated by Louis Martin , who had given them their start in Paris , the duo were soon in demand on stage , in vaudeville and in motion pictures .