A good starter for paella is a traditional Spanish tapas like patatas bravas or Spanish olives.