I have uninstalled other qt versions using brew list, brew remove qt and brew remove qt5. I also noted that I had pyqt installed (and I was not using it), so I also remove it using brew remove pyqt. 
Then, I have reinstalled Qt 5.3.2 and had other issues:
Project ERROR: Xcode not set up properly. You may need to confirm the license agreement by running /usr/bin/xcodebuild.
Which was solved changing the isEmpty($$list($$system("/usr/bin/xcrun -find xcrun 2>/dev/null"))) command from the Qt_install_folder/5.7/clang_64/mkspecs/features/mac/default_pre.prf file to isEmpty($$list($$system("/usr/bin/xcrun -find xcodebuild 2>/dev/null"))), as explained here: Qt Creator - Project ERROR: Xcode not set up properly. You may need to confirm the license agreement by running /usr/bin/xcodebuild
and
Could not resolve SDK path for 'macosx10.8'
That was solved by changing the QtPath/5.3/clang_64/mkspecs/qdevice.pri from !host_build:QMAKE_MAC_SDK = macosx10.8 to !host_build:QMAKE_MAC_SDK = macosx10.12, as explained here: Error: Could not resolve SDK path for 'macosx10.8'
So, I run the command from my Qt directory:
/Users/kuser/Qt5.3.2/5.3/clang_64/bin/macdeployqt MyApplication.app -dmg
and it worked.
I found these solutions in comments from the following question:
Qt5 cannot find platform plugins Mac OS X
Note: this does not solve the macdeployqt error directly, but as it is part of the Qt installation, reinstalling it solved my problem.