Understanding FFT for a vibrational analysis experiment
The following is written assuming you do the signal analysis on your PC, and only use the Arduino to acquire the samples and send them to your PC.
Your Arduino Nano's microcontroller doesn't have the memory necessary to store a second of data.

various sources state that FFT works with 2^n samples

FFTs in length of powers of 2 are especially computationally efficient to compute. Since you probably don't care about how efficient your computation is, you don't care. The FFT is just a fast way to calculate the DFT of a vector, and worst case, any length is possible when just calculating the DFT plain from the textbook formula for the DFT.

This number needs to be 2^n

That's plain wrong. FFTs exist for many lengths, usually for any length that can be decomposed into prime factors &lt; 17. (As far as I know. Maybe we can do better today.)

From my understanding, if I will be measuring accelerations at a constant sample rate of 600Hz for 10 seconds, I will end up with 6000 samples.

That sounds right.

Does this mean that I will have to remove some of the measured data in order to end up with 4096 samples, which meets the 2^n samples condition? Or fill up my samples with zeroes to end up with 8196 samples, which also meets the stated condition?

you can do either, but you don't have to; 6000 = 2·3·10³ = 2⁴·3·5³ and there's multiple FFT implementations for such lengths. Again, you don't even have to use an FFT to calculate the DFT.
So, I'd really rather adjust the FFT (DFT) length to your measurement problem than the other way around.