By fully retrieving all permissions all the time, it will avoid the various Bad Things that happen when you only retrieve a partial package. This would lead to the XML file spuriously growing very large/small simply based on how the tool you're using decided to retrieve your org's metadata (e.g. a partial retrieve would result in a partial permission set, causing artificial changes that you'd have to continually revert, merge, resolve conflicts, etc). In other words, your source control system will be happy, merges will be happy, deployments will be happy (at least, in theory).
This is part of a larger change that's been rumored, where we will eventually be able to point a source control tree at an org and say "make this org exactly as specified from this source control." No more unexpected surprises, since we will be able to literally recreate an org as it existed at any point in the source control system, potentially even to the point of deleting classes, pages, fields, objects, etc. Of course, all of this is part of the new Salesforce DX experience. Salesforce wants developers, particularly ISVs, to have modern deployment capabilities, and a consistent deployment is part of that vision.
It's okay to retrieve from version 40 and deploy as a lower version, but retrieving as a lower version (e.g. 39) and deploying as 40 may delete permissions that were previously set outside of source control. This is a good thing, because we don't like unexpected permissions, but it does mean you need to get a clean retrieve first. Only deploy a file using 40 or above if you are certain it was retrieved from 40 or above. Your package.xml states the version the API runs with. Realistically, this is a once-per-source-control change developers will need to perform.
The Force.com IDE will automatically capture the new permission sets as part of the Upgrade Wizard that pops up with each new release, so there's little danger of something going wrong there. Developers using other systems, like the Migration Toolkit, must make sure that the first thing they do after changing to version 40 is a full refresh before making any permission set-based deployments.
I think you answered your first question on your own. The best way to find out if it can be brought over via a change set is to try. If it doesn't work you'll have to do it manually.
As for the second question, there's a ton of different migration tools out there that could probably migrate the differences without the need to manually remove values in your destination org. Gearset for instance, does a full meta-data compare and allows you to select which meta-data you want to deploy. This would make it very clear what the end result of the deployment will be and should allow you to remove the unwanted values. Gearset does cost money though.
Infact, most of these extra tools would take a little bit of implementation work. If you're only having issues with this one deployment it may not be worth it. Personally, I love gearset (not affiliated). If you're looking for migration tool I'd make sure to put the effort into researching your options and deciding whats best for you.
Best Answer
Permission Set Assignments are data in the org. The DML operation cannot be performed by a Change Set - but this sample code might help you in automating the assignments.