The documentation is a bit misleading. The client ID doesn't technically need to be a UUID hash in that format. It's merely suggesting that format to help people avoid generating duplicate client IDs by accident.
The format of the client ID in analytics.js is a randomly generated 31-bit integer followed by a dot (".") followed by the current time in seconds.
If you wanted to generate a client ID in this format yourself (for whatever reason) you could do something like the following:
var cid = Math.floor(Math.random() * 0x7FFFFFFF) + "." + Math.floor(Date.now() / 1000);
To answer your other question, yes, you can use the same client ID in a server-side Measurement Protocol hit as you find in the cookie generated by analytics.js and the sessions will be linked.
Furthermore, if you wanted to make sure your server-side hits were as closely linked to your client-side hit as possible, you should also use the User Agent and IP override fields, which are new to the measurement protocol. If you don't, then all the geo data for your server-side hits will look like it came from wherever your server is located.
UPDATE
Also, in case it's not clear how to get the client ID from JavaScript, here's what the documentation recommends:
ga(function(tracker) {
var clientId = tracker.get('clientId');
});
Note that it recommends not reading the data directly from the cookie.