Actually, I did my best in my question:
Would speaking Polish with only words that come from Slavic be as hard as trying to speak English with only Anglo-Saxon words?
... to be as Anglo-Saxon as I possibly could. It still looks natural, but it would be next to impossible to say much more without venturing into loan-word country.
The word 'sorry' originates from Germanic *sairig- (the asterisk there means unattested by the way), which developed into Old English: sarig. The original meaning of the word would have been more to do with mental pain, angush rather than the apology or expletive that it later became.
I'd be interested to know the derivation of the word 'przepraszam'.