Aappam is a rice based bread from Southern India. Since it isn't paleo I
omitted it here. But these dishes are paleo:

Side dish for Aappam:
Rich but damn tasty coconut milk curry.
Fry some fennel seeds, cloves, and cardamoms on a tsp of oil. Add
chopped onions, garlic, green chillies, and minced ginger. Add
salt and fry well. Next, add one fresh tomato chopped (optional),
some chopped mint leaves, and some boiled potatoes and/or
cauliflower. Add a pinch of turmeric, and 2 cups of coconut
milk.

Egg curry for Aappam:
Hard boil 2 eggs.
Chop half an onion, 1 large tomato, 4 green chillies, and mince
some ginger and garlic together.
Heat 1 tablespoon of veg. oil. Add 1/3 teaspoon cinnamon powder,
1/2 tsp turmeric, and the onions, and green chillies. Add salt,
and the minced garlic and ginger. Fry till onions turn golden
brown.
Add 1/2 teaspoon red chilli powder (this curry is supposed to be
killer hot, and I would add 1 heaped teasp usually), the tomato
pieces, and fry till pulpy. Slit the eggs from top to bottom
keeping it whole still so that the masala will seep in.
Add eggs to gravy, add 1/3 cup water, and let it evaporate.

Serve hot.

Garlic sambal:
Grind 3 large cloves of garlic, 1/2 tomato (optional), 10 red
chillies roasted in oil or plain roasted, 2 shallots, and 10
raisins till smooth. Add some salt and sesame oil in the end. Mix
well.