You can't use formatting on bytes objects in Python 3.4 or below. Your options are to upgrade to 3.5 or newer, or not use formatting on bytes.
In Python 3.5 and up, you need to make fmt a bytes object; you'd use a bytes literal, and apply the % operator to that:
fmt = b'this is the text: %s' fmt_string = fmt % byte_string
Alternatively, encode the template first, then apply the values:
fmt = 'this is the text: %s' fmt_string = bytes(fmt, 'utf-8') % byte_string
If upgrading is not an option, but your bytes values have a consistent encoding, decode first, then encode again:
fmt = 'this is the text: %s' fmt_string = bytes(fmt % byte_string.decode('utf-8'), 'utf-8')
If you can't decode your bytes values, then your only remaining option is to concatenate bytes objects:
fmt = b'this is the text: ' # no placeholder fmt_string = fmt + byte_string
This will require multiple parts if there is text after the placeholders, of course.