which RPM measurement method is suitable?
At 500 rpm the shaft rotates 8.3333 times per second therefore, in 1 second you count: -

12 x 8.33333 pulses = 100 pulses

At 505 rpm the shaft rotates 8.416667 times per second therefore, in 1 second you count: -

12 x 8.41667 pulses = 101 pulses

You want greater resolution so you can add more bolts BUT to get a resolution of 1 rpm you'll need 5 x 12 bolts and that sounds impractical.

You could do a rolling count over a 5 seconds and each second throw away the oldest 1 second count and introduce the newest count but you'll still have a sluggish mechanism for measuring rpm - changes in speed won't be seen as dynamically as you might want.

Alternatively you use a high frequency clock and measure the number of counts between pulses. You can average 12 results (one full revolution) to reduce positional errors of the bolts.

How fast can you clock and count?

Answer - you have a clock with period 256usecs - this means it toggles 3906 times in one second. If you count these clock toggles for every 12 pulses on the proximity sensor (aka one revolution of the shaft), at 500 rpm you'll count for 0.12 seconds and accumulate a total of 469 clock cycles. If you accumulated 468 clock cycles, this would be the equivalent of 501 rpm.

You, of course have the option of counting two or more revolutions to give greater resolution at higher speeds. At significantly lower speeds you might want to revert to counting proximity pulses per second OR clock counts for a fractional rotation of the shaft.