How to determine DC motor voltage
What type of machine brushed?


  Does this make sense? Would the same current cause the motors to spin
  at different speeds, if the voltage was different? If so, how do I
  figure out what voltage to use?


The speed of the machine is proportional to the voltage applied

The torque the machine can oppose is proportional to the current it sinks.

How to determine?  if the previous controller used 24V, for now I would not consider using a higher voltage. Once you can determine the specific's of the machine (partnumber) you may find you can apply higher voltage as it can support higher speeds. 


  Or could it be that I'm sending the same voltage, but the difference in PWM frequency from my controller and the existing controller is the problem?


Frequency or duty?  for a fixed duty, increasing the frequency will actually reduce the voltage (as the % of the switching time &amp; interlock becomes a bigger contributor). For a different duty then yes as the average voltage will be different. 

As to the actual title question How to determine DC motor voltage

Either from the datasheet of the part in question or Backdriving the machine to determine the \$k_e\$ constant (although without knowing the top speed you could damage the bearings)

\$V = K_e * \omega\$