A producer has stated that a character called "The Shadowman" was going to appear in the film. The character was going to be a god-like being who put Paul Blart through his trials. After a great amount of discussion, it was decided that they remove the character, seeing that the studio wanted to keep the film grounded in reality.
Kevin James had personally called up Vic Dibitetto, with a private number listed, to play Gino Chizetti. James had told Dibitetto that he was so entertained by his YouTube videos that he created the character based on his viral work.
As Paul Blart takes a look at the boxes to Hamburg you can see the address as being in "Hamburg am Main", a combination of Hamburg and Frankfurt am Main. The zip code is from the latter city. The street name is given as Alte Fälschergasse which means "old forger lane".
When Paul says, "Is it hot in here, or did I order my uniform from Rochester Big & Humid", this is a reference to Rochester, New York, which is a very humid city and used to have a store called Rochester Big & Tall.