Glue and Lamination:
Most wood glues are going to be totally fine to put together a paddle. E.g., Titebond II (a pretty ubiquitous and waterproof wood glue) is FDA approved for indirect food contact (meaning it's fine to glue together pieces that will be in contact with food) and retains plenty of its strength at mash temperatures.
Any hard wood should be fine, particularly if you finish it well. Home Depot and Lowes both carry maple and oak, which would be good choices: they're sturdy and look nice. You should have no trouble finding 1x4 and 1x6 boards, which would be perfect for a mash paddle, depending on your design intent. Obviously a lumber supplier would have a greater variety, but if you're not picky about the exact species and don't need very much, it's hard to beat the convenience of the big box stores.
The only treated wood that you should avoid is pressure-treated soft lumber, but it's usually obvious and will probably not come in the dimensions you're looking for anyway. Pressure-treated wood has sort of a green/gray color to it, and is usually sold in long 2x4s or posts. For a small sturdy project like this I would recommend hard wood anyway.
While you don't strictly need to finish the wood, I would strongly recommend it. It will make the wood easier to clean, prevent wood dust and splinters from getting in your mash, and make the wood last much longer. Unfinished wood can't really be cleaned, so plan on getting some woody taste in the mash and some mash stain on the paddle.
The obvious options for finishing a wood mash paddle are a polyurethane or some sort of butcher block oil / wax. Personally I'd do several good coats of polyurethane, which will give you a hard, durable, and waterproof seal. Polyurethane is food safe (but check the label to be sure). Polyurethane comes in a range of glossy or flat finishes, although they'll all be a bit hard and glossy.
Butcher block wax or some other oil rub will give the wood a more natural look, but it won't be quite as durable. You generally have to reapply these finishes periodically, since they wear off and/or soak into the wood. It's conceivable that some of the wax would come off in the mash, but they're totally safe and I'm sure it's a very small amount anyway.