With modern awks, you can just do it like you would in C (though the justification is less clear; C doesn't have the trivial in-line string concatenation that awk does), like so:
maxlen=0
for (i in arr)
if (maxlen<length(arr[i]))
maxlen=length(arr[i])
for (i in arr)
printf("%-*s %s\n",maxlen,arr[i],i)
With old awks, just do it like you would do if you didn't know about %* (this would be much more painful to do in C), like so:
maxlen=0
for (i in arr)
if (maxlen<length(arr[i]))
maxlen=length(arr[i])
printfstring="%-" maxlen "s %s\n";
for (i in arr)
printf(printfstring,arr[i],i)