I have an AT91SAM9263EK where I added an 8MB NOR Flash.
I would like to start the Linux Kernel directly from there but I have troubles with the size of the kernel image.

I configured linux kernel 2.6.38 to boot from NOR flash and built it with "make xipImage"
Building went fine, but the image size is over 16MB, whereas the vmlinux binary is only 4.3MB big.
What causes the image getting that big?

Isn't the regular linux kernel image compressed? To execute in place it can't be compressed. You'd need to look more carefully to see if all the 4 to 16MB comes from that, but could easily explain half of it.

Look at the XIP binary, it should be evident if there is lots of repeating data patterns. Try ZIPing the 16MB binary and see how small it gets, as this will provide a good indicator of the entropy.

I already had a look into it and it was mostly filled up with zeroes from around the offset of 4MB to the end.