Hrothgar is right about "fitz", it is a corruption of the northern French pronunciation of "fils", 'son'. And yes, it was generally used for acknowledged bastard sons of royalty.
You get Tre- Pol- and Pen- names in Scotland too; we spoke a p-celtic language south of the highland line at least for a long time... off the top of my head near me there are Traprain (tref y pren, farmstead of the tree) and Penicuik (pen y gog, cuckoo's end). I can't think of a definite Pol- one offhand... Polwarth maybe but I'm not sure about that.