Ok, I finally fixed it using the reddit thread info and another thread on the apple forum.
https://www.reddit.com/r/AppleFitnessPlus/comments/kds64h/ipad_air_2_looking_for_apple_watch_for_fitness/
Overall what i did is,
1) Installed and opened Home app on iPhone
2) Installed and opened Home app on Ipad
3) Made sure in General - Icloud, keychain was selected to backup on both iPhone and iPad
4) Deleted fitness app on Ipad
5) logged out of icloud on ipad
5)Logged back in to icloud on ipad
6) Installed the fitness app again
7)Verified that I am still logged in on appledId/Icloud on phone (for some reason it asked my password again there)
8) Opened Fitness on iPad and it found my watch.
WHY does it take so many steps to get this to work i have no clue. Also some steps might have not been necessary but i do not know which one, so i wrote all steps I did.