Here's a simple and fast system for placing locations of interest in a single hex on a grid. I am assuming a four hour watch as the basic unit of travel movement. Hexes can be divided into six equilateral triangles, for anyone who didn't know that.
1) Number the six triangles of the hex in clockwise order starting from the top
2) Roll a d6 and a d4
3) The d6 determines which sub-triangle of the hex the location is in. The d4 determines how many hours of travel into that triangle the location is (4 is the centre).
Variant: You could use d4-1 if you prefer fewer things in the centre and more things by the edge.
That's it, that's the whole system. I find it very fast in practice, and you can use a simple notation in your key to track this that looks like:
AA:17 Haunted Castle (1:3)
where "AA:17" is the hex coordinates and "1:3" is sub-triangle and hours of travel in.
When the PCs search a hex randomly, they either pick one of the six sub-triangles, or the referee can roll a d6 for which sub-triangle they search if they have no preference. I make each search take a single watch.
The speed really helps here with populating a lot of content into hexes.