Palette hacking is slightly more involved than anything you've done before. Odds are you'll need an emulator with debugging functions, or at the very least a palette viewer (and the ability to view the associated hex); you might be able to search out the palette data in the ROM and change it to match Mario's color scheme. As for putting Mario in Castlevania, the can of worms you're going to open ranges from "100-calorie pack" to "family size" depending on what exactly you mean by that statement.

100-Calorie Pack of Worms: Copying Mario's sprite over Simon Belmont, putting a whip in his hand and calling it done. Changing the palette is the only hard part, unless you want to change the collision detection as well (since IIRC Simon's sprite is a good deal larger than Mario's), and since Mario doesn't have any whipping animation (or stair-climbing, for that matter) you'll have to draw your own.

Family Size Can of Worms: Not only putting Mario in Castlevania, but making him play like Mario, i.e. killing enemies by jumping on them, leaping tall buildings in a single bound, finding Fire Flowers in candlesticks, etc. This would be a hacking nightmare and it would generally be easier to simply hack Castlevania graphics back into an SMB ROM if this is the effect you want (though it still wouldn't exactly be hacking-free, and the enemy and boss AI would be limited to what's already in the games unless you're a programming virtuoso).

First off, you shouldn't be using Tile Layer Pro. Use Tile Molestor instead. It's cranky and has its quibbles, but it's the much better graphics app.

Second off, try scrolling to the end of the ROM. NES games usually have their graphics all bundled up at the end.

Unless they don't use CHR-ROM

Simon in CV1 (PRG0) starts at offset 0x05038.  You may have had trouble finding it because of the +8.