We have seen that reassigning the lands of an extinct houses falls to both:
- The respective Lord Paramount.
- The Crown
For example, see House Hornwood. Lord Halys and his heir were slain fighting the Lannisters which meant an end of legitimate male line of that family. It fell to Winterfell to decide who will be the next Lord Hornwood. Candidates were nephew of Lord Hornwood by his sister (Whose father offered that he'll take Hornwood name if chosen the heir) Beren Tallhart and Larence Snow, Lord Hornwood's bastard. But of course it must be noted that Robb had declared himself King in the North at that point. So you could say "the Crown" decided the fate of the Hornwood lands. But did that duty fall to Robb simply because of his declaration? Or was it always his duty? We do not know.
We have plenty of examples where the Crown decided who gets the lands of extinct Houses. For example, take Harrenhal. The Crown periodically assigned it to new houses on extinction of the previous holders e.g. Harroways, Towers, Strongs, Lothstons etc.
Since the overwhelming pattern says the crown decides, Let's just assume that is true and the authority of the Lords Paramount doesn't extend to settling cases of extinct houses. Do bear in mind however, the case of Reynes. Lord Tywin wiped out that house when it rose in rebellion. King Aerys did not intervene. Later, King Robert and his hands did not seek to reassign the lands either. It was later when Tywin himself was hand to King Tommen that Castle Castamere was granted to House Spicer for their role in fall of the Young Wolf.
Now specifically for House Tarly, Lord Randyll Tarly's male line might be extinct (Given Dickon's death and Sam's vows) but he still had a number of daughters (Even if we dismiss the possibility of Randyll's brothers, uncles, cousins etc). Either one of them can inherit the Castle Hornhill in absence of a male claimant. If either one of them has a son, that boy can take the name of his grandfather and become the next Lord Tarly. Similarly, any man who marries any of the Tarly girls can take the name Tarly as well. See this answer for details