Andrew,
<<Also a bit disappointed about chocolate because of the dairy (I hope cocoa beans and coffee beans are not legumes) !!>>
NOT that coffee or chocolate are considered paleo by most people but... the dairy issue with chocolate is easily sorted by eating dark chocolate with at least 70% cocoa mass with no vegetable fat [always hydrogenated] and preferably organic such as Green & Black which I know you can get in the US if that's where you live.
Dedy