Is it possible to change font colors in the terminal, without impacting printf's "%*s" padding format?

You're making this a lot more complicated than it should be. You can handle alignment with $message and not care about the width of ANSI sequences:

#! /usr/bin/env bash

message() {
    [ x"$2" = xOK ] && color=2 || color=1
    let offset=$(tput cols)-4-${#2}
    printf "%-*s[ %s%s%s ]\n" $offset "$1" "$(tput setaf "$color")"  "$2" "$(tput sgr0)"
}  

message "install font library" "OK"
message "update configuration file on server" "ERR"

Edit: Please note that most printf(1) implementations don't cope well with lengths calculations for multibyte charsets. So if you want to print messages with accented characters in UTF-8 you might need a different approach. shrug