The reason the FET turns off so slowly is because you only have 2 kΩ pulling it high. Take a look at the datasheet for that FET. It should show you the actual and effective gate capacitance when switching. The relatively weak 2 kΩ pullup is working against that capacitance.
Here is a trick I sometimes use in this situation:
The double emitter follower is basically a impedance buffer. The current to charge and discharge the gate capacitance is handled by Q1 and Q2, so the signal at GATE can be much higher impedance and still switch the FET quickly. Note that this double emitter follower will loose 700 mV or so on each end. That is fine for a FET that switches over a 10 V gate range. It will still be "off" with 700 mV on the gate just as well as with 0. At the other end, its usually easy enough to drive GATE the extra 700 mV further than what you want to make sure shows up on the gate of Q3.
Olin Lathrop has identified your problem, but the solution is pretty simple
simulate this circuit – Schematic created using CircuitLab
A simple level shifter (Q1) will provide a good 12 volt swing on MOSFET gate. With a gate capacitance in the range of 1500 pF, transition time will be less than a microsecond, so at 1 kHz the power wasted will be very small. The transition time will be great enough, though, that there is no need for a separate gate resistor.
With about 8 mA (4V/500 ohms) base drive and 60 mA collector current (12V/200 ohms) Q1 will be adequately saturated.
With a greater PWM frequency you'd need to start looking at more sophisticated drivers, but I don't see the need here.
ETA - Also, you asked about switcher noise. On the one hand, your inductor is doing a pretty good job of keeping peak current within the power supply limits. On the other hand, the 470 uF capacitor is producing 100 amp plus current spikes (for an ideal cap), so that probably has something to do with it.
FURTHER EDIT - The OP asked how to size the components for a level shifter.
First, the BC639 data sheet gives a maximum collector current of 1 amp. Start with an assumption of 1/10 to 1/20 of that, or 50 to 100 mA. The transistor will be used as a switch, not an amplifier, either full on (zero voltage across it, more or less) or full off (no current). This mode is called saturation, and you should assume a current gain of about 10. For amplifiers, a BC639 can run with a gain of about 40 to 250, but this does not apply in this case. A gain of 10 which produces a collector current of 50 to 100 ma implies a base current of 5 to 10 mA. Assuming the Arduino can supply its rated current at nearly a full 5 volts, this says that the base resistor will drop about 4 volts, since the base-emitter junction will drop about 0.7 volts. 500 ohms is a convenient value, and this will provide 8 mA of base drive. 8 mA of base drive times 10 gives a collector current of 80 mA when the transistor is on. Since we're driving the transistor hard on, this says that the collector resistor (the load resistor) will drop about 12 volts. If R2 were 1k, you'd get 12 mA, so 200 ohms (another convenient number) will give about 60 mA. This says that the transistor will operate with a gain of 7.5. Close enough. Note that none of these values is real picky. You can easily ignore 20% slop.
If a 2-stage level shifter is needed in order to maintain the phase relationship between the input voltage and the load current, this is easily done. However, the resistor values can be a bit higher on the first stage in order to cut down of power dissipation. This is because the load resistor of the first stage will provide the base drive for the second, and this is fed by 12 volts rather than 5. If you do this, it's a good idea to place a resistor from each base to ground, with a value of about 10 times the base resistor. This is just to make sure that the transistors stay turned off with no input.
However, it's not clear at all why you'd need a second stage. All you need to do is adjust the PWM timing in software to give the right result, and this should be very straightforward.
Best Answer
The transistor unmounted on a heatsink has a thermal resistance of 62 degC per watt. That is how much it will heat up if dissipating a watt of power.
5 volts at 2 amps is 10 watts and losses in the MOSFET of about 1 watt (or a little more) are a likely scenario. Modern buck regulators are quite often quoted as having an efficiency of around 95% and a home spun one will be somewhat worse than this at around 90% so, I don't think your MOSFET is doing anything out of the ordinary.
It might continue to warm of course so you should consider mounting it on a small heatsink. Note that it does have a maximum operating temperature of 175 degC.