¿Es posible hacer una eliminación con una cláusula HAVING?

Realmente no. La cláusula de tener implica una agregación, lo que significa que ya no tiene las filas originales.

Creo que quieres lo siguiente:

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