I am not sure if this place is nation wide but here in Kansas City, MO, there is a fast food place called The Mixx. They carry all kinds of salad and have a create your own salad(which is great for strict paleo). Their salmon is amazing and grilled right in front of you. They also have sandwiches which came in handy because my girlfriend does not use but supports the paleo lifestyle. Just an FYI post for those in the area looking for somewhere quick and easy to get a great paleo friendly meal.

Hope this helps!