In these two sentences, I would've thought に would be used in place, but instead を is used? When is it appropriate to use either?
A: 反対側【はんたいがわ】50メートルあたりを探【さが】して！ Search around 50 metres on the opposite side!
B: もし会【あ】ったらグレースをどうするつもりですか？ What are you planning to do to Grace if we see her?
Shouldn't に be used in both of these to indicate the direction?
Well, generally every language has some quirks in its grammar, but as for your examples, を is the only option and に is never used. I sense from your statement "I would've thought に would be used in place, but instead を is used" that you may think or be taught that case particles each represent some kind of "universal" trait, but they are actually decided by loose conventional rules much like English choice of prepositions, that you can't make nearly perfect prediction from its meaning.
A: 反対側50メートルあたりを探して！
探す indeed has two kinds of noun alignment: [target]を[place]で探す and [place]を探す but neither can take に. You wouldn't see it except as a part of adverb: 効率的に探す.
B: もし会ったらグレースをどうするつもりですか？
Don't be fooled by the English translation. The answer you expect for "What do you do to Grace?" would usually not be "I do [noun] to Grace." but "I [verb] Grace.", isn't it? In that case, you use the phrase "do what" to asking another verb; it is a pro-verb, more specifically, interrogative verb.
English speakers have to work around the lack of pure interrogative verb by forming an expression "do what" (i.e. "what" as dummy object) and push the original object out as indirect "to" argument. Japanese doesn't have one either, but fortunately we have どうする (どう is an adverb) that doesn't take up the object slot, so that the true object remains the object.
グレースをどうするつもりですか？ vs What are you going to do to Grace?
グレースを家に帰します vs I will send Grace back home.
I read that に is used for indicating places of existence, target recipient [of something], the occasion, or the source of receiving an item. (There may be some I have missed.) I also read that を is for objects of a transitive verb (meaning a verb that needs something to receive the action it indicates). If I remember or know correctly, の is used before a prepositional noun like 横｛よこ｝(side)、近｛ちか｝く(near)、東｛ひがし｝(east)、南｛みなみ｝(south)、北｛きた｝(north)、or 西｛にし｝(west) in examples such as フィリピンの南｛みなみ｝(South of the Philippines)、日本｛にほん｝の北(North of Japan)、電車｛でんしゃ｝の近く(Near the train) 、 etcetera. I hope this helps.
