The surest way to resolve this is to create a fresh Photos Library by following these steps:

1. ⌘ cmd-Q out of Photos.
2. Go into  → System Preferences → iCloud → Photos Options… and uncheck iCloud Photo Library.
3. Reboot if you want to be safe, though it shouldn’t be necessary.
4. Launch Photos with ⌥ opt-click.
5. Click Create New… and name your new Photos Library.
6. Go into Photos → Preferences → General and click Use as System Photo Library.
7. Go into Photos → Preferences → iCloud and check iCloud Photo Library.
8. Wait for your photos to be redownloaded from iCloud.

If you’d rather try to keep your existing Photos Library, follow these steps instead:

1. ⌘ cmd-Q out of Photos.
2. Create a backup of your Photos Library.photoslibrary file.
3. Launch Photos with ⌘ cmd-⌥ opt-click.
4. Click Repair.
5. Wait for macOS to repair your Photos Library. A full sync should take place once the repair has completed.

Some screenshots courtesy of OS X Daily.

I believe you are misunderstanding how My Photo Stream works. It is intended as a temporary (up to 30 days or 1000 photos at any given time) mechanism to allow each photo you take to sync to each of your devices - iOS, Mac and Windows. There is also a limit of 1000 photos in My Photo Stream at any given time. As new photos are uploaded, older ones are deleted.

"Why is not everything backed up": If you have more than 1000 photos in your Camera Roll, the oldest X (greater than 1000) photos will no longer appear in My Photo Stream. Similarly, photos older than 30 days will be removed. Again, My Photo Stream is not a backup service. This could explain storage size discrepancies, as could the fact that videos are not uploaded to My Photo Stream.

"Why are photos in iCloud taking up space on my phone": My Photo Stream stores a copy of each photo that is in the stream on your device. Generally speaking, an identical photo that is in multiple places should only take up space once on your device - if the same 100KB photo is in Camera Roll and My Photo Stream, there are two pointers to the same 100KB file on the device, instead of having two files that are 100KB each. That said, the storage is not freed up until all pointers are removed from the device. If you delete a 100KB photo from Camera Roll, but it still exists in Photo Stream, that 100KB will still be used.

Also, if you have started or joined any shared Photo Streams, that will take up space as well.