"He left the restaurant without paying."
Translation:Él se fue del restaurante sin pagar.
"Pagando" is mainly used with estar in a different set of verb tenses, including present progressive ("I am paying," like you're doing it as you say it. "Pagar", as the infinitive, means both "to pay" and "paying". Since the main verb of the sentence is "left" and not directly linked to the paying itself, the infinitve (verb not conjugated) needs to be used here to translate "without paying".
...I wrote this early in the morning, so please let me know if it doesn't make any sense.