I got a paper rejected even if the associated editor and the referees liked the paper - it was more of a question of fit. Now I am sending the paper to a similar ranked journal that might be a better fit for the paper. The anonymous referee gave lots of good constructive feedback. Should I thank him in the new version? I am reluctant to it for two reasons. First, the referees or editor at the new journal might correctly infer that the paper was rejected elsewhere and that might bias them against the paper. Secondly, even if the referee was anonymous, given his tastes and comments, I am almost sure he is someone I already thanked in the paper but of course I can not be 100% certain of it.
Your first concern is pretty close to the point. I really see no benefit in thanking the reviewers in a subsequent submission of the paper. It just takes you pretty close to a grey area where theoretically no harm would be done, but in practice there is often some degree of bias involved. Again, no benefit, only potential harm.
I don't see a gray area here at all. If someone has helped improve your paper, you must acknowledge their contributions, either by co-authorship, citation, or acknowledgment. Yes, even in the submission. Yes, even if there is some small chance that the new referees will notice that your paper was rejected elsewhere and will let that fact unprofessionally bias their review.
Even if your submission is double-blind, you can always thank ███ █████ and ██████ ██ for their helpful comments on an earlier version of the paper.
Less forcefully: It is never a mistake to sincerely express gratitude.
even if the referee was anonymous, given his tastes and comments, I am almost sure he is someone I already thanked in the paper but of course I can not be 100% certain of it.
You are not supposed to know who the referee is. So don't guess; just thank the anonymous referee. There is absolutely no harm in acknowledging the same person twice, once by name and once in their role as anonymous referee.