I need to stay at 10.3.1 Desktop for some 3rd party add-ins but I'd like to upgrade Server to 10.4. I'm moving from a physical to a virtual server, seems like a good time to update to 10.4.
Compatibility of ArcGIS 10.4.1 for Server with earlier versions—Documentation | ArcGIS Enterprise
Hope this helps!!!
On different machines, you should have no problem. But if you install Desktop on the Server, I would keep it the same. I believe that is still recommended (although not sure if it is required or unusable).
Typically when you start upgrading, they are at different versions during that process, and things work, but if you have any issues, that would probably be what would be pointed out first.
SDE doesn't need to be at the same level, database wise, but there are minimum requirements for that based on you version too (fir example, SQL2008 will not be supported for Desktop 10.5 SDE databases.