Your two suggestions prompted me to do a speed comparison between them and the result surprised me.

I tried:

import random
nums = [random.randint(0, 255) for n in range(10000000)]

then timed the simple:

for n in nums:
    hx = '%X' % n  # or hx = format(n, 'X')

I also tested a number of more complex formats like:
hx = '%{:02X}'.format(n) vs hx = '%%%02X' % n

In all cases, the old vs new formatting styles are rather similar in speed in my system Python 2.7.6 (with maybe a slight advantage for the format-based formatting).
In Python 3.5.0, however, old-style %-formatting is much speedier than under Python 2, while new-style formatting doesn't appear to have changed much, with the result that %-formatting is now between 30-50% faster than format-based formatting.

So I guess my questions are:

- are my timings wrong?

and if not:

- how got %-formatting improved (generally? or for %X specifically?)
- can this speed up be transferred to format-based formatting somehow?