Вам не нужно уничтожать ярлык, даже ничто не заставляет вас это делать, и не создавайте его динамически. Вы можете создать это, когда вам это нужно, или поляна может сделать это для вас. Это минимальный пример, но, как вы заметили, обе метки создаются только один раз.
import gtk
labels = []
def changeLabel(widget):
l = p.get_children()[1]
p.remove(l)
nl = labels[l is l1]
p.add2(nl)
w = gtk.Window()
w.connect('destroy', lambda w: gtk.main_quit())
p = gtk.HPaned()
w.add(p)
b = gtk.Button('change label')
b.connect('clicked', changeLabel)
p.add1(b)
l1 = gtk.Label('hello world')
l1.show()
p.add2(l1)
l2 = gtk.Label('ciao mondo')
l2.show()
labels = [l1, l2]
which = 0
w.show_all()
gtk.main()