Is it safe to use signed messages from a private key to send to clients as tokens?
They should be. As long as your signature scheme is resistant to existential or at least selective forgery, [under chosen message attack]. Well, I am not sure if the scheme requires resistance to forgery under chosen message attack unless you set up your application in which your server works as a signing oracle but no worries, most state of the art signature schemes are resistant to existential forgery under chosen message attack. As long as you don't use outdated signature schemes, the ones that hash the message directly using MD5 or SHA1, the signature can be forged by creating hash collisions.
In fact that's what popular JWT tokens are. They are just base64 encoded json objects with some content (like who it is issued to, expiry time etc),which may or may not be encrypted, and appended with a signature of that content produced using server's private key (or alternatively contains a MAC of the object produced using a key secret to the server but this method has a disadvantage in that no one else can verify the authenticity of the token).