Technically, the Arduino<->bt-module (UART) and the bt<->bt (wireless) baud rates could be different, but this would result in malfunctions due to overflow: a continuous dataflow of, say, 115200 bits per second coming through the wireless interface could not be retransmitted to the Arduino over a 9600 baud UART interface, even if there were some buffering mechanism in between, and you would experience data loss. So I expect that setting the baud rate on the UART interface automatically changes the baud rate on the wireless interface, though I cannot tell for sure.
What I call “command mode” is a state of the module where you can send AT commands to the module through the UART interface. These commands are not retransmitted to the wireless interface. As far as I understand, this is the only way to change the baud rate on the module (the SoftwareSerial.begin(baudrate) in the Arduino sketch only sets the speed of the SoftwareSerial interface, on the Arduino side of the link). The AT+BAUD8 command sets the baud rate to 115200 on the UART, and should be followed by a new SoftwareSerial.begin(115200). This change should be persistent (preserved after reset).
In order to enter command mode a pin of the module should be set to high (connected to 3.3V) before power up. There may be a way to do that in software, but I think the sketch you used to set the baud rate just failed to change anything, and the module is still working at the default 9600. Did you try SoftwareSerial.begin(9600)? It should test my supposition pretty quickly.
Finally, do not connect the module to the PC Usb because the voltage coming out of the PC is higher than the 3.3 V used by the module, both for power and signal (tx/rx). The same applies to the RS-232 adapter. I think however that you can try this:
- Load a simple sketch (such as blink) that does not use Serial (no Serial.open(), print(), read()). This may even be overkill given what follows, but doesn’t hurt.
- While the Arduino is disconnected from Usb, connect Arduino RX - BT TXD, Ard TX - BT RXD, Ard 3V3 - BT VCC, Ard GND - BT GND.
- Connect the Arduino and press the RESET button (of the Arduino). Keep it pressed until the end of the test.
- Open putty and try connecting to the serial port of the Arduino. See if you get something from the BT module.
The principle is the same used for the loopback test: do not let the Arduino take control of the UART (com interface). After that you may also try releasing the RESET button and see what happens. Perhaps, not using Serial, the sketch will just ignore what happens to the com interface.
Last point is an explanation of my phrase about buffers and interrupts: the hardware serial interface (UART) relies on interrupts to see if there are bytes to send or read. Interrupts are small routines that run independently from the main sketch and are activated by the processor itself when some event occurs. For example, if there is incoming transmission on the serial line the UART will notify the processor of the presence of data (in the UART buffer), and the processor will activate an interrupt service routine to read it. Once read, the character will be moved to the Serial input buffer (a memory location) and removed from the UART buffer. Finally, when the sketch executes Serial.read() (or something similar) the character is removed from the Serial input buffer and passed to the sketch. If you have two processes sharing the same serial line they will use the same UART, and interrupts, and buffers, but only the first one of them will be able to get the character using Serial.read(). Actually it’s a bit more complicated than that, but I hope it’s more understandable.
 I failed to notice that the module lists a VCC range of 3.6V–6V, so you should use the 5V of the Uno (you already use it, I guess), and the idea of dissecting a Usb cable may work. Sorry, there are variants based on the same chip and I happen to own one using 3.3V.