Order of the reaction between hemoglobin and oxygen
You seem to be overthinking this a great deal. The order of a reaction is not defined by the units of the rate constant, but rather by the sum of the exponents in the empirical rate equation. From the IUPAC Gold Book:


  If the macroscopic (observed, empirical or phenomenological) rate of reaction ($v$) for any reaction can be expressed by an empirical differential rate equation (or rate law) which contains a factor of the form $k[\ce{A}]^\alpha[\ce{B}]^\beta\cdots$ [...] then the reaction is said to be of [...] (total or overall) order $n = \alpha + \beta + \cdots$


Considering that the partial pressure of $\ce{O2}$ is directly proportional to its concentration, the forward reaction has a rate equation

$$k'[\ce{Hb}][\ce{O2}]$$

where the proportionality factor between $P(\ce{O2})$ and $[\ce{O2}]$ is absorbed into the new rate constant $k'$. The order is simply 2.