Well, there is some preliminary evidence that eating enough fat (1, 2), specifically monounsaturated and saturated fat (3) can lead to higher free testosterone levels.
The same seems to be true of eating meat (4, 5, 10), although in at least one of those studies the effect may have been due to the testosterone lowering effect of soy (6). Hey, I guess avoiding soy is pretty paleo though, right?
There is also some evidence that diets high in protein relative to carbohydrates may lower testosterone (3, 7, 8). If you're eating plenty of paleo approved carbs this probably doesn't affect you.
A deficiency of zinc, a mineral found richly in meat, appears well demonstrated to lower testosterone levels (11, 12, 13), an effect which is reversed upon taking in adequate zinc. Oh yeah and zinc absorption appears to be improved by eating paleo; it's increased by meat protein and decreased by phytic acid, casein, soy protein (14).
There's also some evidence from rat studies that a deficiency of vitamin A, that compound commended by liver lovers, can depress testosterone levels (15, 16). Also, a study of male twins found a correlation between vitamin A intake and testosterone levels (17).
I'm sure there are numerous other examples, but these are several notable reasons why a paleo diet may increase testosterone levels.