Tic tac toe.
Jotto. Still a word game but more fun than hangman in my opinion.
This, with my ten year old.
It’s better now that she’s older - when she was smaller, she’d draw something, then insist we take the stained mat home with us, which didn’t happen very often.
At least once my husband (fellow Doper AndyL) used a placemat to teach me some calculus.
Spill stuff on them, if anything. I’m a messy eater.
Depending on the restaurant, I sometimes ask for the kids’ menu, which comes on a placemat. If I think I can get away with it, I’ll ask for crayons and color. Otherwise, I don’t do anything.
Sheldon Cooper posts on the Dope! 
We like to play hangman on the paper mats. Any other time I’d scoff at the idea of playing hangman but in a restaurant with a paper placemat I’m all about playing hangman.
I don’t have spellcheck on this computer. At least, nothing I can figure out (I’m not much better at tech stuff than I am at spelling).
Hangman or dot and boxes, rarely tic tac toe.