È possibile eseguire un'eliminazione con una clausola HAVING?

Non proprio. La clausola having implica un'aggregazione, il che significa che non hai più le righe originali.

Penso che tu voglia quanto segue:

DELETE from UserPredictions
where UserId in (select UserId from UserPredictions group by UserId having count(*) < 500)