It is worth it though because of the much better error handling in Promises and the ability to use async/await which makes error handling even more easy to get correct.

I'd suggest making all functions that take callbacks also return Promises to make the transition easier:

    async function fetchFirstUser(iswhatIwant, callback) {
      const safeCallback = (user) => {
        try {
          callback(user);
        } catch (e) {
          console.error(e);
        }
      };

      try {
        const user = await knex.first().from("users");
        safeCallback(user);
        return user;
      } catch (e) {
        safeCallback(null);
        throw e;
      }
    }

You can put this in a utility (and I'd recommend standardizing on Node's callback style):

    async doWithCallback(promise, callback) {
      const safeCallback = (error, result) => {
        if (callback == null) {
          return;
        }
        try {
          callback(null, result);
        } catch (e) {
          console.error(e);
        }
      };
      try {
        const result = await promise;
        safeCallback(null, result);
        return result;
      } catch (e) {
        safeCallback(e);
        throw e;
      }
    }

    async function fetchFirstUser(iswhatIwant, callback) {
      return doWithCallback(knex.first().from("users"), callback);
    }

At some point you can start warning when callbacks are passed in, then throwing, then remove the argument.

You don't need to refactor the existing code. You can change the calling code.

    // Promisifying a standard callback
    const myAsyncMethod = Bluebird.promisify(myCallbackMethod);

    // Or if you have weird callback passing and need
    // to manipulate the callback method being passed around
    function myAsyncMethod(...args) {
        return Bluebird.fromCallback(cb => myAsyncMethod(cb, ...args));
    }