Break RSA without padding using a rainbow table attack

Yes, the attack in the question would work for the low modulo of the example. The term "dictionary" is more appropriate than "rainbow table" (used in the context of making a compact table of precomputed hashes).

Actual attacks can't work this way though. In RSA as practiced it's impossible to build a large-enough dictionary, as it would take too much time to build (proportional to the modulus $n$, which is typically at least 2048-bit nowadays). However, if Alice encrypted a message known to belong to a small set (such as the names on the class roll) directly with textbook RSA $m\mapsto c:=m^e\bmod n$, then it is possible to decrypt $c$ by encrypting each possible message and testing which matches $c$. A sequential search of the $m$ in the class roll will do: a dictionary of the corresponding $c$ is only useful if there are several messages (and RSA is not practically used by breaking messages into small chunks, as in the question).

Random encryption padding solves this problem, by reversibly turning a message $m$ into a sufficiently random-like message representative $\widetilde m\in[0,n)$. Then textbook RSA can be safely applied to $\widetilde m$, per the RSA assumption: for proper public key $(n,e)$ and random $x\in[0,n)$, it's hard to find $x$ from $x^e\bmod n$.

how can the decryptor (Bob) 'remove' those random bits if he doesn't know them?

The big picture is there is a convention between Alice and Bob about which bits of $\widetilde m$ are padding (some of which random) added by Alice, that should be removed by Bob. That simplified description is quite close to the deprecated padding technique in RSAES-PKCS1-v1_5. The modern RSAES-OAEP has extra steps so all except (at most) 8 bits of $\widetilde m$ appear random even when $m$ is not (which is obtained by a reversible symmetric cryptographic transformation after applying random padding, which diffuse the randomness), but the idea remains.