I'll collect the comments and build an answer from that.
[..] you just perform the operation, say, a thousand times for
keys with similar security properties and record the time for each.
Note that the speed is rather implementation dependent, so you're
measuring the implementations of the algorithm rather than just the
of course life and code development would be too simple with this, so
[Y]ou also need to consider [..] the quality
of the implementations. If you coded them yourself, do you know about
the implementation tricks for both algorithms that a quality
implementation would use? Comparing naive implementations might not
tell you very much.
and still of course security developement has its own special issues which need to be respected before comparing speed:
In addition to the above, it is not just the optimization level of the
implementation that matters, but e.g. resistance to side channel
attacks, so in some cases an implementation could even be faster than
a good implementation.
So the logical conclusion is ...
If you want to compare RSA and Paillier encryption algorithms, then
you shouldn't compare two implementations of those algorithms, you
should compare the computational complexity of the algorithms.
with this helpful comment on how to do so:
In this case, one thing to consider is the different length of the
modulus and numbers involved (In Paillier, calculations are done with
numbers twice as long, if the same $n$ is used, due to $\bmod n^2$).
Credits to Maarten, poncho, otus, user2768 and tylo for this joint effort of an answer.