Always double-check with the staff for Paleo compliance, but usually, you can take advantage of the eggs, fruit, and breakfast meat provided at your hotel.