I remember walking by a Brazilian churrascaria (steakhouse with skewered meat served tableside) in the area. I googled "churrascaria London Paddington" and Rodizio Rico appeared. Checked the map and it's the one I remember. It's on Westbourne Grove about a half mile from Paddington. Haven't eaten there so I can't offer an opinion on the food but it's truly a different experience.

http://www.rodiziorico.com/