You could set up IPSEC with certificates on the affected machines, possibly in conjunction with NAP and use the Windows Firewall to filter RDP traffic which is coming in unencrypted.
Here is a walkthrough for a scenario which is similar to your request but using preshared keys instead of certificates.
But keep in mind that "creating a certificate and copying this to all computers" is a bad idea all in itself - you obviously should create one certificate per client and set up your access rules accordingly. This ensures confidentiality of your connections along with the possibility to revoke certificates as they get lost / disclosed without breaking other machine's connections.
Edit: something that might look tempting is setting up a Remote Desktop Gateway (basically an HTTPS tunnel gateway for RDP) and require client certificate authentication upon SSL connection setup via the IIS properties (the Gateway is implemented as an ASP.NET application within IIS). This however seems to be unsupported by the Remote Desktop Client - there is no way to provide a client certificate for a proxied connection.