I see that the mikroElektronika boards have an on-board USB programmer, does PBP work with that programmer or would I still need a Pickit 2?
PBP generates standard Intel .HEX files that work with pretty much any decent PIC programmer out there.

As for the pickit 2 I see two available, a starter kit and Debug Express debugger which of those should I be looking at?
The Debug Express version comes with a 44-pin surface mount 16F887 on a demo board that allows in-circuit debug. The starter kit comes with a DIP socket allowing 8/14/20-pin mid-range PICs to be used on the demo board.

If you're just getting started, the starter kit is probably your best option. Note: You will still want to grab a good PIC programmer like an MeLabs U2 for programming in-circuit, and the 840Z ZIF adapter which lets you program PICs from 8 to 40-pin packages.

I've had to re-flash my PICkit2 twice since I started using it. It uses a USB boot-loader, and is relatively easy to corrupt, so you'll want a device programmer to re-flash the PICkit2. Just in case. Once you corrupt the boot-loader on a PICkit2, it's worthless until you can re-program it.

Concerning the Leap form Basic Stamp to PIC I don't see much difference so I figure I'm missing something. If I use PBP and a PIC what's so different from the Stamp? The biggest differences I see are: no on-board voltage regulator, no direct RS232 com.
The BIG differences are speed of code execution, tons of built-in hardware peripherals like A/D, hardware PWM, comparators, hardware USART, timers, counters, etc. PICs have these built-in, a Stamp doesn't.

The Stamp compiler creates tokens, then downloads your tokenized code to an external EEPROM. This really slows things down. PBP creates a .HEX file, which is programmed directly into the PIC. This speeds things up. A PIC running at only 4MHz can execute 4 million single-cycle instructions per second. There's a BIG difference.

PicBasic Pro syntax is similar to the BS2. PBC is similar to the older BS1 syntax. I recommend you get PBP from the start.

Doesn't a programmer and debugger do what the RS232 did on the stamp?
Most PIC programmers do nothing but program your code into the PIC. The PICkit2 offers a few extra bells & whistles for serial communications, in-circuit debug, etc, but you'll still want to have a good device programmer handy that can do in-circuit programming and has a ZIF (zero insertion force) socket.

The MeLabs U2 USB programmer is excellent. They normally have support for new PICs ready & tested before you can even get engineering samples from Microchip.