This is a good start. And I like the little characters.
Mathias has a point about it not looking like the vatican (or any real place), but it can work in a gamey kinda setting.
You said you want to keep it simple and whatnot, but if you are using a set palette and not care for the original restrictions you might as well try and use it to its full potential
I made an edit of some bits:

- Any organically tiling tile should start from a good base tile. This means for stuff that wraps around (like the stones) the base tile should look pretty good both when tiling as well as solitary.
- For this reason I shifted the main rock tile around a bit so that it does not have any odd single pixel lines of tops, bottoms or sides of stones (it had one I think)
- You have added some variation tiles in your tileset, but all you did was darken (remove) or brighten one of the stones. In most cases this does not work as well as redrawing the inside of the tile. Make sure it still maintains a good tiling with the other tiles in the set that are relevant.
- I also made side tiles for the rocks and corner tiles. You have corner tiles but they look a bit unconvincing and it's obvious they are just a shaved off version of the tile you already have, making the corners a bit more unique helps. Basically in most cases it is better to redraw most of a tile if it is a variation.
- On he stones and blocks you have a directional upper left lightsource, as well as the cast shadows, but the pillars are super flat.
- Also made a variation tile for the block. Tiles like this should have usually at least 3 or 4 variations because if you have the same banged up block all over the place it looks weird (a lot weirder than the same clean and new looking block all over the place). Basically having broken things look regularly broken does not work, same goes for your pillars.
- For the background I made only one basetile and then went over it with for the shadows. This generates more tiles than you have at the moment but it looks more convincing. Also I think you should keep the dither to a minimum on high contrast palettes like this.
- For variation I just deleted one or 2 stones from the base tile. This works quite well in this case since it is a simple 2 colour tile without much detail to begin with.
- As for the colours, the nice thing about the C64 colours is that you can form a lot of ramps.
here are some examples:

trying to just do a grey stone with grey colours or a grey pillar with grey colours or whatever with whatever base colour does not do you any favour if you want stuff to have some life. You can see I tried to keep a main colour tone in all the tiles to suggest material and/or colour.
The stones use mainly the mid grey,light brown and purple colour, but still foremost look grey/brown. Same goes for the pillars which look grey/white and the rocks which look like some dark stone. - Was this a palette with more colours or not limited you would have to make some of the stuff to fit more to each other, but since everything is using the same 16 colours this pretty much guarantees that things gel nicely.
- You used 2 new greys, which I felt were not really needed in this case. I you wanted to make the characters stand out more you could have a single pixel black outline around them (but not where they touch the ground)
I hope this helps, if you have any questions just ask
