Использование понимания списка и форматированных строк (Python 3.6 +):
df['new'] = [f'{i:02d}{j:03d}' for i, j in df[['C1', 'C2']].values]
print(df)
C1 C2 new
0 8 49 08049
F-строки часто улучшают производительность:
df = pd.concat([df]*100000)
%timeit [f'{i:02d}{j:03d}' for i, j in df[['C1', 'C2']].values] # 458ms / loop
%timeit [str(i).zfill(2)+str(j).zfill(3) for i, j in df[['C1', 'C2']].values] # 1.03s / loop
%timeit df.C1.astype(str).str.zfill(2) + df.astype(str).C2.str.zfill(3) # 1.02s / loop