Well, the trick here is that you have to contact each computer and ask it to rename itself. It then updates its account in AD. There's no way to just make the change in AD.
The Rename-Computer command can do it. Exactly how you use it depends. What kind of connectivity do you have to the computers? How will you come up with their new names?
This can be a big deal, too. I don't know anything about your environment, but there may be other dependencies on computers' names. You could potentially affect user profiles, potentially affect certain permissions – there are things that could go wrong. I'm not going to be able to solve all of that for you, I just want to make sure you're aware that this isn't a 100% safe operation in some environments.
You don't necessarily have to use a startup script, although that might be the easiest way to ensure that each computer actually does the change. You'll have to get the current computer name ($env:computername) and exit the script if the computer name is already the way you want. If not, you can use Rename-Computer. Note that Rename-Computer is, I believe, in PowerShell v3 and later. You'd have to use something different (like NETDOM) if your computers have an older version of PowerShell.